贪心3.
转换问题：gas[i]-cost[i]=每个加油站能够带来的net gas数目。只要使net gas之和永远>=0就能达到题目要求了。因为题目说只要有解就是唯一解，所以只要找出gas[]-cost[]这个数组的最大连续子数组就可以了。
思路类似最大连续子数组，只要区间和为负数就扔掉。
但这题还有可能无解，所以要跟踪一个汽油的deficit。如果最后获得的net gas抵不上之前的deficit就返回-1。
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
diff = []
for i in range(len(gas)):
diff.append(gas[i]-cost[i])
startindex = -inf
sum = 0
deficit = 0
for i in range(len(diff)):
if sum+diff[i] < 0:
startindex = -inf
deficit += (sum+diff[i])
sum = 0
continue
else:
if startindex == -inf:
startindex = i
sum += diff[i]
return startindex if sum >= -deficit else -1
这个贪心策略的难点还是第二次反向的贪心遍历。第一次从左到右遍历，保证评分高的右孩子永远比左边的拿糖多；第二次从右到左遍历，在保证第一次结论不变的情况下再保证评分高的左孩子永远比右边的拿糖多。第二次的关键是使用max函数来保证第一次结论不变。
def candy(self, ratings: List[int]) -> int:
candyVec = [1] * len(ratings)
for i in range(1, len(ratings)):
if ratings[i] > ratings[i - 1]:
candyVec[i] = candyVec[i - 1] + 1
for j in range(len(ratings) - 2, -1, -1):
if ratings[j] > ratings[j + 1]:
candyVec[j] = max(candyVec[j], candyVec[j + 1] + 1)
return sum(candyVec)
和上题类似，本题又是有h和k两个维度。两个维度要逐个击破，先选h进行排序。
由于本题的k，意义是前面站着的比自己身高高或者相等的人数，所以应该按身高倒序排列。
接下来是最关键的一步：按照每个人的k插入res[k]的位置，就可以完成排序！这是因为经过前面的排序，任意人的前面站着的都是比自己高的！
接下来还有一个坑就是插入到res[k]的位置。众所周知，array的随意插入最坏要花O(n)的时间，所以最好是插入一个linked list。不过看上去python对list insertion的支持还行。
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
people.sort(key=lambda x:(-x[0],x[1]))
res = []
for p in people:
res.insert(p[1], p)
return res
这题的想法同样很巧妙，我gg。
多维度的贪心，需要逐个击破。最好是发现两个维度的某种内在联系，就像406一样，数组的排序和每个人的k有隐含的联系。