局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置。
- 时间复杂度：O(n)
- 空间复杂度：O(1)
1 class Solution: 2 def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: 3 curSum = 0 # 当前累计的剩余油量 4 totalSum = 0 # 总剩余油量 5 start = 0 # 起始位置 6 7 for i in range(len(gas)): 8 curSum += gas[i] - cost[i] 9 totalSum += gas[i] - cost[i] 10 11 if curSum < 0: # 当前累计剩余油量curSum小于0 12 start = i + 1 # 起始位置更新为i+1 13 curSum = 0 # curSum重新从0开始累计 14 15 if totalSum < 0: 16 return -1 # 总剩余油量totalSum小于0，说明无法环绕一圈 17 return start
1. 一定是要确定一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边，如果两边一起考虑一定会顾此失彼。
2. 局部最优：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果。
- 时间复杂度: O(n)
- 空间复杂度: O(n)
1 class Solution: 2 def candy(self, ratings: List[int]) -> int: 3 candyVec = [1] * len(ratings) 4 5 # 从前向后遍历，处理右侧比左侧评分高的情况 6 for i in range(1, len(ratings)): 7 if ratings[i] > ratings[i - 1]: 8 candyVec[i] = candyVec[i - 1] + 1 9 10 # 从后向前遍历，处理左侧比右侧评分高的情况 11 for i in range(len(ratings) - 2, -1, -1): 12 if ratings[i] > ratings[i + 1]: 13 candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1) 14 15 # 统计结果 16 result = sum(candyVec) 17 return result