406. 根据身高重建队列 135. 分发糖果 两个维度一起考虑的贪心

作者

406. 根据身高重建队列

  2. class Solution:
  3.     def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
  4.         people.sort(key=lambda x: (-x[0],x[1]) )
  5.         deq=[]
  6.         for i in people:
  7.             deq.insert(i[1],i)
  8.         return deq、

局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性

全局最优：最后都做完插入操作，整个队列满足题目队列属性

好难想的题目

两个维度一起考虑的情况，还有一道题：135. 分发糖果

  1. class Solution:
  2.     def candy(self, ratings: List[int]) -> int:
  3.         n=len(ratings)
  4.         sz=[1]*n
  5.         for i in range(1,n):
  6.             if ratings[i]>ratings[i-1]:
  7.                 sz[i]=sz[i-1]+1
  8.         for i in range(n-2,-1,-1):
  9.             if ratings[i]>ratings[i+1]:
  10.                 sz[i]=max(sz[i],sz[i+1]+1)
  11.         return sum(sz)
  • 一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
  • 一次是从右到左遍历，只比较左边孩子评分比右边大的情况。

发表评论