题目描述
每人至少 1 颗糖；评分更高的要比相邻的拿更多。求满足规则的最少糖果总数。
思路解析
只从左往右扫，能保证「比左邻居高就多给」，但右邻居比我矮、我却没多给的情况就漏了。一个方向永远盖不住两个邻居。
左扫只管「比左邻居高就 +1」，右扫只管「比右邻居高就 +1」。同一个人在两遍里各得一个值，取较大的那个，就同时满足了左右两条规则。
准备 · 人手一颗：先给每个人发 1 颗糖，满足「至少 1 颗」。格子里显示的是评分 ratings，candy 数组先全为 1。
左扫 · 起点 i=0：左扫从下标 0 开始。最左边的人没有左邻居可比，糖数就是初始的 1。指针往右走，逐个和左邻居比。
左扫 · i=1：从左往右。i=1 的评分 0 没有比左边的 1 高，不满足「更高」，不加糖，candy[1] 还是 1。这就是负例：评分不升时保持原样。
左扫 · i=2：i=2 的评分 2 大于左边的 0，要比左邻居多拿，于是 candy[2] = candy[1]+1 = 2。左扫结束，candy = [1, 1, 2]。
左扫完成：左扫只盯左邻居。现在 candy=[1,1,2]，但右边规则还没管——比如 i=0 的 1 大于 i=1 的 0，却只拿了 1 颗，还不够。该右扫了。
右扫 · i=1：从右往左。i=1 的评分 0 不大于右边的 2，右扫不加，仍是 1。和左扫值 1 取较大 → candy[1] 仍是 1。
右扫 · i=0 · 关键：关键一步：i=0 的评分 1 大于右边的 0，右扫给它 2。和左扫的 1 取较大得 2——这正是左扫漏掉、右扫补上的那颗糖。
完成 · 求和：i=2 右扫不变仍 3。最终 candy = [2, 1, 3]，每人都同时满足左右规则，糖果总数 = 5。
左右两条规则纠缠在一起难处理。拆成「只管左」「只管右」两遍各自贪心，最后取 max 合并，互不干扰——这是处理双向约束的通用招。
参考代码（Python）
1def candy(ratings):
2 n = len(ratings)
3 candy = [1] * n # 每人先发 1 颗
4 for i in range(1, n): # 左扫：只看左邻居
5 if ratings[i] > ratings[i - 1]: # 比左邻居高
6 candy[i] = candy[i - 1] + 1
7 for i in range(n - 2, -1, -1): # 右扫：只看右邻居
8 if ratings[i] > ratings[i + 1]: # 比右邻居高
9 candy[i] = max(candy[i], candy[i + 1] + 1) # 取较大
10 return sum(candy)复杂度分析
- 时间复杂度：O(n) —— 左右各扫一遍，共两遍线性
- 空间复杂度：O(n) —— 额外一个 candy 数组记每人糖数
套路模板
记住骨架：正向赋值、反向取 max。凡是「同时受左右邻居约束」的题都能套这个双向扫描。
1res = [1] * n
2for i in range(1, n): # 正向：满足左约束
3 if 左条件: res[i] = res[i-1] + 1
4for i in range(n-2, -1, -1): # 反向：满足右约束
5 if 右条件: res[i] = max(res[i], res[i+1] + 1)
6# 反向必须 max，否则会冲掉正向的结果易错点
- 错误写法：只扫一遍（或反向直接赋值不取 max） → 正确写法：左右各一遍，反向用 max 合并（一遍只保左约束；反向若直接赋值会冲掉左扫结果，[1,0,2] 会算成 [1,1,3]，i=0 漏了一颗）
- 错误写法：评分相等时也给对方多加一颗 → 正确写法：只有「严格大于」才加，相等保持各自的值（题目只要求「更高的更多」，相等不需要谁多拿，多加会浪费糖果且不符规则）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。