柱状图中最大的矩形
题目链接：84. 柱状图中最大的矩形 - 力扣（LeetCode）
思路：掌握了……吗？还是参考了下官网思路。代码随想录 (programmercarl.com)
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int result = 0;
stack<int> st;
heights.insert(heights.begin(), 0); // 数组头部加入元素0
heights.push_back(0); // 数组尾部加入元素0
st.push(0);
for(int i=1;i<heights.size();i++){
if(heights[i]>heights[st.top()]){
st.push(i);
}else if(heights[i]==heights[st.top()]){
st.pop();
st.push(i);
}else{
while(!st.empty()&&heights[i]<heights[st.top()]){
int mid=st.top();
st.pop();
if(!st.empty()){
int left=st.top();
int right=i;
int w=right-left-1;
result=max(result,w*heights[mid]);
}
}
st.push(i);
}
}
return result;
}
};