8.30 - 高算3

这节课主要讲heap,stack和deque的运用。heap主要是保持顺序上，每次取出一个元素还可以保持剩下元素的最大值最小值，插入和删除操作都是log n，stack有四种用处，暂时保存有效信息，可以用反转，可以用来模拟dfs的栈空间，最后也是常考的，用来保持单调性

1. Expression Expand： 利用stack，题目倒是不难，只是要考虑的corner case太多，看着wrong answer来调程序，最终还是AC了

2. Trapping Rain Water: 好像和stack或者heap无关，找出每一个点的左边最大值和右边最大值

3. Implement Queue by Two Stacks：比较普通的一道题

4. Min Stack： 利用两个stack

5. Sliding Window Median：利用heap，只是在python里没有hashheap这个东西，可以利用lazy pop的方法

6. Trapping Rain Water II： 把周围的一圈做为heap的初始值，然后pop出最小，并且把最小值四周的值加入进入，加入的时候要注意加入的高度是两个高度的较大那个，用一个visited矩阵来维护访问过的值

7. Largest Rectangle in Histogram: 最大矩形，用一个stack来维护单调递增的，如果碰到一个小的，就pop出一个值，以pop出值为高度的矩形的左右边界就是刚加入的index和stack里前一个index的值。

8. Maximal Rectangle： 这题的解法是最大矩形的扩展，把每一行做为底边，求最大矩形，然后找到其中的最大值。

9. Data Stream Median：比那个sliding window median容易一些，不需要朝外pop值

10. Sliding Window Maximum： 用一个deque来维护一个单调递减序列

11. Max Tree：stack里维护一个递减的node序列，如果新进来的node比较大的话，就一直pop，把pop出的最后一个元素设为新进node的左子树，并且把新进元素设为上一个stack里当前最后一个元素的右子树。也就是说，stack维护的递减node序列就当前值是前一个值的右节点

12. 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暂存值用到极致了吧，手写手写！！