84 柱状图中最大的矩形
思路：该解决方案使用堆栈来跟踪可能形成最大矩形的连续高度的索引。我们将输入高度数组的前面和后面各插入一个高度为0的柱子，以确保堆栈中的所有元素都可以弹出。然后，我们从左到右遍历每个高度，并将当前高度的索引压入堆栈。如果当前高度小于堆栈顶部高度，则我们已经找到了一个可能的矩形。我们弹出堆栈顶部高度，并计算矩形的面积。矩形面积可以通过弹出高度的索引和当前堆栈顶部高度的索引之间的距离减去1得到宽度，高度为弹出高度的高度。我们将所有矩形面积的最大值相加，即可得到最大矩形的面积。
1.单调栈
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> st;
heights.insert(heights.begin(), 0);
heights.push_back(0);
st.push(0);
int result = 0;
for(int i = 1; i < heights.size(); i++){
while(heights[i] < heights[st.top()]){
int mid = st.top();
st.pop();
int w = i - st.top() - 1;
int h = heights[mid];
result = max(result, w * h);
}
st.push(i);
}
return result;
}
};
