Largest Rectangle in Histogram (Lintcode 122, Leetcode 84)

这道题运用了单调栈的思想。单调栈的用法是：用来找数组，左边或右边，第一个比当前元素小（或者大）的是谁。即insert前，栈顶的元素。

这道题的trick是，栈中存的不是元素，而是数组index，这样才方便计算面积.

解法一：从左往右+从右往左扫两遍，分别找比当前元素小的。然后用map统计结果

int largestRectangleArea(vector<int> &height) {
    // write your code here
    if(height.empty()) return 0;
    stack<int> st;
    unordered_map<int, int> mp;
    for(int i=0; i<height.size(); i++){
        while(!st.empty() && height[st.top()] >= height[i]){
            st.pop();
        }
        if(!st.empty()) mp[i] += height[i] * (i - st.top());
        else mp[i] += height[i] * (i+1);
        st.push(i);
    }
    stack<int> st2;
    for(int i=height.size()-1; i>=0; i--){
        while(!st2.empty() && height[st2.top()] >= height[i]){
            st2.pop();
        }
        if(!st2.empty()) mp[i] += height[i] * (st2.top() - 1 - i);
        else mp[i] += height[i] * (height.size() - 1 - i);
        st2.push(i);
    }
    int max_ret = 0;
    for(auto it : mp){
        max_ret = max(max_ret, it.second);
    }
    return max_ret;
    
}

解法二：九章的解法，想法更加巧妙。push的时候不计算面积，而pop的时候才计算面积。最后要push一个-1进去，来把最小元素pop出来。这样扫一遍就可以搞定。注意，计算面积，是pop当前index之后，由剩下的边作为终止边，然后要横轴需要减一。

class Solution {
public:
    /**
     * @param height: A list of integer
     * @return: The area of largest rectangle in the histogram
     */
    int largestRectangleArea(vector<int> &height) {
        // write your code here
        if(height.empty()) return 0;
        height.insert(height.begin(), -1);
        height.push_back(-1);
        stack<int> st;
        int max_ret = 0;
        for(int i=0; i<height.size(); i++){
            while(!st.empty() && height[st.top()] > height[i]){
                int h = height[st.top()]; st.pop();
                max_ret = max(max_ret, (i - st.top() - 1) * h);
            }
            st.push(i);
        }
        return max_ret;
    }
};