力扣题解84.柱状图中最大的矩形

思路看题解

动态规划版本

class Solution {
public:
    int largestRectangleArea(vector& heights) {
        int n = heights.size();
        if (n == 0) return 0;
        if (n == 1) return heights[0];
        // 存储向左，向右第一个比heights[i]小的下标
        int dp_l[n], dp_r[n];
        dp_l[0] = -1, dp_r[n - 1] = n; //哨兵
        for (int i = 1; i < n; i++) {
            int k = i - 1;
            while (k >= 0 && heights[k] >= heights[i]) k = dp_l[k];
            dp_l[i] = k;
        }
        for (int i = n - 2; i >= 0; i--) {
            int k = i + 1;
            while (k < n && heights[k] >= heights[i]) k = dp_r[k];
            dp_r[i] = k;
        }
        int ma = -1;

        for (int i = 0; i < n; i++) {
            ma = max(ma, heights[i] * (dp_r[i] - dp_l[i] - 1));
        }
        return ma;
    }

};

单调栈版本

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack <pair<int, int> > s; //构建一个单调递增的栈
        pair <int, int> tp(-1, -1);
        s.push(tp);
        int ans = -1;
        for (int i = 0; i < (int)heights.size(); i++) {
            while (heights[i] < s.top().first) { // 每次出栈都求一下以其为高的矩形最大面积
                tp = s.top();
                s.pop();
                ans = max((i - s.top().second - 1) * tp.first, ans);
            }
            tp = pair<int, int> (heights[i], i);
            s.push(tp); //入栈
        }
        while (s.size() != 1) { 
            tp = s.top();
            s.pop();
            ans = max(((int)heights.size() - s.top().second - 1) * tp.first, ans);
        }
    return ans;
    }

};