這節(jié)課主要講heap,stack和deque的運用。heap主要是保持順序上，每次取出一個元素還可以保持剩下元素的最大值最小值，插入和刪除操作都是log n，stack有四種用處，暫時保存有效信息，可以用反轉(zhuǎn)，可以用來模擬dfs的?？臻g，最后也是?？嫉?，用來保持單調(diào)性

1. Expression Expand： 利用stack，題目倒是不難，只是要考慮的corner case太多，看著wrong answer來調(diào)程序，最終還是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來維護單調(diào)遞增的，如果碰到一個小的，就pop出一個值，以pop出值為高度的矩形的左右邊界就是剛加入的index和stack里前一個index的值。

8. Maximal Rectangle： 這題的解法是最大矩形的擴展，把每一行做為底邊，求最大矩形，然后找到其中的最大值。

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

10. Sliding Window Maximum： 用一個deque來維護一個單調(diào)遞減序列

11. Max Tree：stack里維護一個遞減的node序列，如果新進來的node比較大的話，就一直pop，把pop出的最后一個元素設為新進node的左子樹，并且把新進元素設為上一個stack里當前最后一個元素的右子樹。也就是說，stack維護的遞減node序列就當前值是前一個值的右節(jié)點

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直到最后，不過有些細節(jié)要寫寫，覺得面試碰到這種題算倒霉吧。。

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暫存值用到極致了吧，手寫手寫??！