LeetCode84：柱形图中最大的矩形

题目描述
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

代码
单调栈

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
         
        stack<int> stk;
        heights.insert(heights.begin(), 0);
        heights.push_back(0);

        
        stk.push(0);
        int result = 0;
        for (int i = 1; i < heights.size(); i++) {
            //遍历元素小于当前栈顶元素的时候就是收获结果的时候
            while (heights[i] < heights[stk.top()]) {

                //当前所取的柱形高度
                int h = heights[stk.top()];
                stk.pop();

                //此时的stk.top()就是比mid小的元素下标
                int w = i - stk.top() - 1;

                result = max(w * h,result);
            }
            stk.push(i);
        }
        return result;
    }
};