84. 柱状图中最大的矩形

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if(!heights.size()) return 0;
        heights.push_back(0);
        heights.insert(heights.begin(), 0);
        int n = heights.size();
        vector<int> dp(n);
        stack<int> idx; //要增 一到变小了，就要把前面的都弄掉了
        int res = 0;
        for(int i = 0; i < n; i++)
        {
            while(idx.size() && heights[i] < heights[idx.top()])
            {
                auto tmp = idx.top();
                idx.pop();
                res = max(res, (i - idx.top() - 1) * heights[tmp]);
            }
            idx.push(i);
        }
        return res;
    }
};

第二次写题
用dp的原因是，这个高度只能是柱子的高度，然后就是要去计算区间的长度；
这里要注意的就是这个区间的长度怎么计算

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.insert(heights.begin(), -1);
        heights.push_back(-1);
        vector<int> v = vector<int>(heights.size(), 0);
        stack<int> stk; //存的是idx
        for(int i = 0; i < heights.size(); i++)
        {
            while(stk.size() && heights[stk.top()] > heights[i])
            {
                int idx = stk.top();
                stk.pop();
                v[idx] = heights[idx] * (i - stk.top() - 1);
            }
            stk.push(i);
        }
        int res = 0;
        for(int i = 0; i < heights.size() - 1; i++)
            res = max(res, v[i]);
        return res;
    }
};