1、最初是用最大子矩阵求解，不过TLE

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int len=height.size();
        vector<int> L(len);
        vector<int> R(len,len);
        vector<int> sortH(height);
        sort(sortH.begin(),sortH.end());
        int result=0;
        
        for(int i=0;i<sortH.size();i++){
            int left=0,right=len;
            for(int j=0;j<len;j++){
                if(height[j]>=sortH[i]){
                    L[j]=max(L[j],left);
                }
                else {
                    left=j+1;
                    L[j]=0;R[j]=len;
                }
            }
            for(int j=len-1;j>=0;j--){
                if(height[j]>=sortH[i]){
                    R[j]=min(R[j],right);
                    result=max(result,sortH[i]*(R[j]-L[j]));
                }
                else right=j;
            }
        }
        return result;
    }
};

有个用栈实现的方法很好

struct node{
    int height;
    int index;
    node(int h,int i):height(h),index(i){}
};
class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        if(height.empty())return 0;
        int len=height.size();
        int result=0;
        stack<node> st;
        for(int i=0;i<len;i++){
            if(st.empty()||height[i]>st.top().height){
                st.push(node(height[i],i));
            }
            else if(height[i]<st.top().height){
                int lastIndex=0;
                while(!st.empty()&&height[i]<st.top().height){
                    lastIndex=st.top().index;
                    result=max(result,st.top().height*(i-lastIndex));
                    st.pop();
                }
                st.push(node(height[i],lastIndex));
            }
        }
        while(!st.empty()){
            result=max(result,st.top().height*(len-st.top().index));
            st.pop();
        }
        return result;
    }
};

LeetCode OJ:Largest Rectangle in Histogram