每日一题 LCR 039. 柱状图中最大的矩形

LCR 039. 柱状图中最大的矩形

是由单调栈

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.insert(heights.begin(),0);
        heights.push_back(0);
        int ans = 0;
        stack<int> stk;
        for(int i=0;i<heights.size();++i){
            while(!stk.empty() && heights[stk.top()] > heights[i]){
                int r = stk.top();
                stk.pop();
                int area = (i - stk.top() -1 ) * heights[r];
                ans = max(ans,area);
            }
            stk.push(i);
        }
        return ans; 
    }
};

使用动态规划更容易理解

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> dpl(n,0);
        vector<int> dpr(n,0);
        stack<int> stk;
        for(int i=0;i<n;++i){
            while(!stk.empty() && heights[stk.top()] >= heights[i]){
                stk.pop();
            }
            dpl[i] = stk.empty() ? -1 : stk.top();
            stk.push(i);
        }
        while(!stk.empty()) stk.pop();
        for(int i=n-1;i>=0;--i){
            while(!stk.empty() && heights[stk.top()] >= heights[i]){
                stk.pop();
            }
            dpr[i] = stk.empty() ? n :stk.top();
            stk.push(i);
        }

        int ans = 0;
        for(int i=0;i<n;++i){
            int area  = (dpr[i] - dpl[i]-1) * heights[i];
            ans = max(ans,area);
        }
        return ans;
    }
};