LeetCode84. 柱状图中的最大的矩形
题目链接：84. 柱状图中的最大的矩形
独上高楼，望尽天涯路
感觉和接雨水很像。
慕然回首，灯火阑珊处
思路如下。
我们可以遍历每根柱子，以当前柱子 i 的高度作为矩形的高，那么矩形的宽度边界即为向左找到第一个高度小于当前柱体 i 的柱体，向右找到第一个高度小于当前柱体 i 的柱体，其中宽度不包含左右第一个高度小于当前柱体i的柱体）。
代码实现上唯一和接雨水不同的是，因为求的是第一个小于，所以需要在heights数组首尾插入元素0，防止遇到递增或者递减的heights数组，导致无法计算result。
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> st;
heights.insert(heights.begin(), 0); // 数组头部加入元素0
heights.push_back(0); // 数组尾部加入元素0
st.push(0);
int result = 0;
for (int i = 1; i < heights.size(); i++) {
while (heights[i] < heights[st.top()]) { // 因为heights首插入了0，所以不需要判断单调栈是否为空
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;
}
};