定義：單調棧就是棧內元素單調遞增或者單調遞減的棧，單調棧只能在棧頂操作。(棧內可以存相應元素的數組下標)

單調棧的維護是 O(n) 級的時間復雜度，因為所有元素只會進入棧一次，并且出棧后再也不會進棧了。

eg：遞增棧

　　對于當前元素，如果它的值>棧頂 ： 直接入棧

 　　　　　　　　  如果它的值<棧頂 ： 從棧頂循環pop，直到當前值>棧頂  (找到棧中第一個小于當前值的位置)

性質：

1.單調棧里的元素具有單調性，得到的是當前元素左邊小于或大于當前值的有序數列

2.元素加入棧前，會在棧頂端把破壞棧單調性的元素都刪除

3.使用單調棧可以找到元素向左遍歷第一個比他小的元素，也可以找到元素向左遍歷第一個比他大的元素

例題：

Trapping Rain Water

Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

這道題要找一個V字型的水洼才能存住水，高度取兩邊最大值的minimum

解法一：從左到右過一遍用數組記錄，統計當前左側的最大高度，從右到左過一遍，統計當前右側的最大高度，再遍歷一遍數組統計儲水量即可

解法二：雙指針，從兩邊向內遍歷，從矮端開始循環統計，更新矮邊

解法三：單調棧，維護遞減棧，當前高度>棧頂，循環統計，注意必須形成V即棧里至少2個元素，為了統計儲水量(長度和高度)棧中存的是下標

Largest Rectangle in Histogram

Given height = [2,1,5,6,2,3],
return 10.

維護遞增棧

補0：為了使得最后一塊板子也被處理，在高度數組最后面補一個0，這樣原先的最后一個板子也可以被處理了

 1 while (i < height.size()) {
 2     if (st.empty() || height[i] > height[st.top()]) {
 3         st.push(i++);
 4     } else {
 5         int t = st.top(); st.pop();
 6         if (st.empty())
 7             res = max(res, height[t] * i);
 8         else
 9             res = max(res, height[t] * (i - st.top() - 1));
10     }
11 }

參考:

Adherer