https://leetcode.com/problems/largest-rectangle-in-histogram/description/
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
Example:
Input: [2,1,5,6,2,3] Output: 10
如圖所示，求圖中最大的長方形面積。
[思路]
觀察一下不難發現，長條形中的任一條，向左右擴張就會變成長方形。例如原題中index 2(高度為5)的長條型，向左右擴張至極限後，就會變成高=5, 寬=2的長方形。
既然題目求最大的長方形，而長方形來自於長條型的擴張，那麼我們就從index 0開始，計算這個長條型可以擴張到多大，然後如法炮製地計算idx 1,2,3,4,5的長方形大小。然後在這六個長方形(idx 0~5所擴張出的長方形)中取最大的就是答案。
這個方法的複雜度是O(N^2)
[進階思路]
上述思路中，長條型可能可以往左或右擴張，所以對於每個長條型，都必須scan&check N-1個人，也就是它左與右的所有人，才會找出對應的長方形。
進階思路的方法是，當你由左往右處理長條型時，不要急著算對應的長方形，相對地你要分case處理。首先準備一個stack，我們之後會把idx push進去，假設H[i]是idx i的高
1.H[i-1] > H[i] : 高度下降了，例如上圖中的H[3] > H[4]，代表idx 3長條型不可能向右擴張了。不僅如此，i左側的長條形只要高度大於H[i]，就是idx2 & 3，這些長條形都無法右擴張超過i。這時候你就有了idx 2,3長條型的擴張的右邊界。
至於左邊界呢，你就去尋找左邊小於你的人，它就是左邊界。例如對於idx3來講，左邊小於你的人是idx2。對於idx2來講，左邊小於你的人是idx1。
有了左右界和高，就可以計算出長方形的大小了。
這些被計算完長方形的長條型，我們都不需要了，所以全都pop() out stack，之後就不用管他們了。接著你再把push(i)，它還沒被計算過，我們還需要它。
2.H[i-1] < H[i] : 高度變大，代表左邊的長條形可以繼續向右延伸。我們把i放入stack中。
3.H[i-1]==H[i] : 高度不變，代表左邊的長條形可以繼續向右延伸。所以H[i-1]其實是多餘的，我們不用紀錄它的idx。我們記錄同樣高度的長條形中，最右邊那個即可。我們把i-1從stack中pop()，然後push(i)。
照這以上1,2,3的步驟，每個idx其實都只會一次而已(push / pop stack一次)，因此時間複雜度是O(1)。
class Solution {
public:
int largestRectangleArea(vector<int>& H) {
int max = 0;
H.push_back(0);//for convinence
stack<int> index;
for(int i = 0; i < H.size(); i++)
{
while(!index.empty() && H[index.top()] > H[i])
{
int h = H[index.top()];
index.pop();//pop it, next top()'s height will smaller than h.
int w = (i-1) - (index.empty() ? -1 : index.top());
int area = h*w;
max = area > max ? area : max;
}
if(!index.empty() && H[index.top()] == H[i])
index.pop(); //pop because i wanna replace it.
index.push(i);
}
return max;
}
};
