第四天(堆)(贪心)

今天完成题目： 1045， 1577，703 1046： 最后一块石头

• a,b=b,a可以快速实现交换

• 使用heapq包来实现堆，但是里面默认只有最小堆

• 也可以使用内置的隐藏函数实现最大堆，速度快但耗内存

• heapq的最大堆没有实现插入后调整的函数

1577：找出最小的n个数

• 继续使用heapq包实现，调用heapq.nsmallest(n, arr)实现，但是速度貌似还能改进

703：数据流中的第k个大的数

• 注意，不一定要用大顶堆，然后找出第k个大

• 使用小顶堆，切割出最大的k个值，之后顶部就是第k个大的值了

heapq包的使用

1. heapq.heapify可以原地把一个list调整成堆[小顶堆] 而 heapq.nlargest 会调成大顶堆

2. heapq.heappop可以弹出堆顶，并重新调整

3. heapq.heappush可以新增元素到堆中，不会调整

4. heapq.heapreplace可以替换堆顶元素，并调整下

5. 为了维持为K的大小，初始化的时候可能需要删减，后面需要做处理就是如果不满K个就新增，否则做替换；

6. heapq其实是对一个list做原地的处理，第一个元素就是最小的，直接返回就是最小的值

贪心算法完成题目： 1221 ，1518 1221：分割平衡字符串

• 没有看清题意，错误理解了平衡字符串一定要对称，写错了

• 后面才发现平衡字符串是指包含的字母数量相同即可，通过balance变量，进行增减，为0时便是一个平衡子串

1518：换酒问题

• 简单，通过整除//和求模%循环一下就出来了，记得理清思路