题目

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;

    }

};