求解最大矩形，很容易想到O（n^2）的解法，只需要求解max(min(height(i...j)*(j-i+1))),0<=i<=j<n;
class Solution {
public:
int largestRectangleArea(vector<int> &height) {
int ans=0,tans=0,len=height.size();
for(int i=0;i<len;i++){
int minh=height[i];
for(int j=0;j<=i;j++){
if(height[j]<minh)minh=height[j];
tans=(j-i+1)*minh;
if(tans>ans)ans=tans;
}
}
return ans;
}
但是对于大的数据超时，通过用栈记录记录，从而将空间复杂度由O(1)到O(n),以空间换时间，将时间复杂度降到O(n)
class Solution {
public:
int largestRectangleArea(vector<int> &height) {
int len=height.size();
if(len==0)return 0;
stack<int >st;
stack<int >index;
int ans=0,tans=0;
for(int i=0;i<len;i++){
if(st.empty()||height[i]>st.top()){//递增的话，放入
st.push(height[i]);
index.push(i);
}else if(st.top()>height[i]){//出现降序
int tindex=0;
while(!st.empty()&&height[i]<st.top()){//计算山头部分的值
tindex=index.top();
index.pop();
tans=st.top()*(i-tindex);
st.pop();
if(tans>ans)ans=tans;//记录最大
}
st.push(height[i]);//记录
index.push(tindex);
}
}
while(!st.empty()){//最后计算各个极小值情况
int tindex=index.top();
index.pop();
tans=st.top()*(len-tindex);
st.pop();
if(tans>ans)ans=tans;
}
return ans;
}
};