1. 084

largest-rectangle-in-histogram/

2. 算法

栈优化：O(n)

http://www.cnblogs.com/felixfang/p/3676193.html http://www.cnblogs.com/ganganloveu/p/4148303.html

3. 代码

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) 
        if(heights.size()==0) return 0;
        int res=0;
        vector<int> temp=heights;
        temp.push_back(0);

        stack<int> s;
        for(int i=0;i<temp.size();i++){
            if(s.empty()||(s.empty() && temp[i]>=temp[s.top()]))
                s.push(i);
        else{
            while(!s.empty() && temp[s.top()]>temp[i]){
                int idx=s.top();
                s.pop();
                int width=s.empty()? i:(i-s.top()-1);
                res=max(res,temp[idx]*width);
            }
            s.push(i);
        }
    }
    return res;
    }
};