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

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

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:
输入: [2,1,5,6,2,3]
输出: 10
https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

代码：

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if(heights.size() == 0) return 0;
        int max = 0;
        stack<int> _stack; // 用于存储下标
        _stack.push(-1);
        // 目标是让栈靠近底部存储高度更小的下标，因为矩形的计算依赖于该范围内的最小高度
        for(int i = 0; i < heights.size(); ++i) {
            if(_stack.size() == 1 || (_stack.top() != -1 && heights[i] >= heights[_stack.top()])) {
                _stack.push(i);
            } else {
                while(_stack.top() != -1  && heights[_stack.top()] > heights[i]) {
                    // 当栈里面的元素大于当前高度的时候，出栈，同时计算面积
                    // 目的是将较小的高度放入栈底
                    int index = _stack.top();
                    int h = heights[_stack.top()];
                    _stack.pop();
                    int s = (i - _stack.top() - 1) * h;
                    // cout<<"while s = "<<s<<endl;
                    max = max > s ? max : s;
                }
                _stack.push(i);
            }
        }
        while(_stack.size() > 2) {
            int index = _stack.top();
            int h = heights[index];
            _stack.pop();   
            int s1 = h * (heights.size() - index); // 右边的面积
            while(_stack.top() != -1 && heights[_stack.top()] >= h)
                _stack.pop();
            int s2 = h * (index - _stack.top() - 1); // 左边的面积
            max = max > (s1 + s2) ? max : (s1 + s2);
        }
        // 最小高度要单独计算
        if(_stack.top() != -1) {
            int s = heights[_stack.top()] * heights.size();
            max = max > s ? max : s;
        }
        return max;
    }
};