这节课主要讲heap,stack和deque的运用。heap主要是保持顺序上，每次取出一个元素还可以保持剩下元素的最大值最小值，插入和删除操作都是log n，stack有四种用处，暂时保存有效信息，可以用反转，可以用来模拟dfs的栈空间，最后也是常考的，用来保持单调性
-
Expression Expand： 利用stack，题目倒是不难，只是要考虑的corner case太多，看着wrong answer来调程序，最终还是AC了
-
Trapping Rain Water: 好像和stack或者heap无关，找出每一个点的左边最大值和右边最大值
-
Implement Queue by Two Stacks：比较普通的一道题
-
Min Stack： 利用两个stack
-
Sliding Window Median：利用heap，只是在python里没有hashheap这个东西，可以利用lazy pop的方法
-
Trapping Rain Water II： 把周围的一圈做为heap的初始值，然后pop出最小，并且把最小值四周的值加入进入，加入的时候要注意加入的高度是两个高度的较大那个，用一个visited矩阵来维护访问过的值
-
Largest Rectangle in Histogram: 最大矩形，用一个stack来维护单调递增的，如果碰到一个小的，就pop出一个值，以pop出值为高度的矩形的左右边界就是刚加入的index和stack里前一个index的值。
-
Maximal Rectangle： 这题的解法是最大矩形的扩展，把每一行做为底边，求最大矩形，然后找到其中的最大值。
-
Data Stream Median：比那个sliding window median容易一些，不需要朝外pop值
-
Sliding Window Maximum： 用一个deque来维护一个单调递减序列
-
Max Tree：stack里维护一个递减的node序列，如果新进来的node比较大的话，就一直pop，把pop出的最后一个元素设为新进node的左子树，并且把新进元素设为上一个stack里当前最后一个元素的右子树。也就是说，stack维护的递减node序列就当前值是前一个值的右节点
-
Building Outline: 一道比较麻烦的题目，利用扫描线和heap，觉得这个解法还不错，不过也不是我能一次写出来的
class Solution(object):
def getSkyline(self, buildings):
"""
:type buildings: List[List[int]]
:rtype: List[List[int]]
"""
def addsky(pos, hei):
if sky[-1][1] != hei:
sky.append([pos, hei])
sky = [[-1,0]]
# possible corner positions
position = set([b[0] for b in buildings] + [b[1] for b in buildings])
# live buildings
live = []
i = 0
for t in sorted(position):
# add the new buildings whose left side is lefter than position t
# 先把较小的building都加进去
while i < len(buildings) and buildings[i][0] <= t and buildings[i][1] > t:
heapq.heappush(live, (-buildings[i][2], buildings[i][1]))
i += 1
# remove the past buildings whose right side is lefter than position t
# 再把不符合的building都pop出来
while live and live[0][1] <= t:
heapq.heappop(live)
# pick the highest existing building at this moment
h = -live[0][0] if live else 0
addsky(t, h)
return sky[1:]
13. Heapify: heap里的siftdown的操作，对arr的每一个值，找到2*i+1和2*i+2的比较小的值，并且swap，不停swap直到最后，不过有些细节要写写，觉得面试碰到这种题算倒霉吧。。
class Solution:
def heapify(self, A):
# write your code here
for i in reversed(range(len(A)/2 + 1)):
self.siftdown(A, i)
def siftdown(self, A, k):
while k < len(A):
smallest = k
if k * 2 + 1 < len(A) and A[k * 2 + 1] < A[smallest]:
smallest = k * 2 + 1
if k * 2 + 2 < len(A) and A[k * 2 + 2] < A[smallest]:
smallest = k * 2 + 2
if smallest == k:
break
A[k], A[smallest] = A[smallest], A[k]
k = smallest
14. Expression Tree Build: 好麻烦，算是stack暂存值用到极致了吧，手写手写！！
网友评论