84柱状图中的最大矩形

题目描述

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

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

问题分析

单调栈模板

stack<int> st;
for(int i = 0; i < nums.size(); i++)
{
    while(!st.empty() && st.top() > nums[i])
    {
        st.pop();
    }
    st.push(nums[i]);
}

• 利用单调栈求出当前柱状左右最近小的柱状高度，一次来计算面积
• 暴力遍历求解

解题思路1

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

        mono_stack = stack<int>();
        for (int i = n - 1; i >= 0; --i) {
            while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
                mono_stack.pop();
            }
            right[i] = (mono_stack.empty() ? n : mono_stack.top());
            mono_stack.push(i);
        }
        
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
};

解题思路2

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {

        int area = 0;
        
        for (int left = 0; left < heights.size(); ++left)
        {
            //每次遍历都要重新计算
            int H = INT_MAX;
            int W = 0;
            for (int right = left; right < heights.size(); ++right)
            {
                H = min(H, heights[right]);
                W = right - left + 1;
                area = max(area, W*H);
            }
        }
        return area;
    }
};