1.题目

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
 

2.思路解析

• 单调栈+常数优化
• 用left和right记录左右边界
• 单调栈就是从数组中找到左右两边比你大的数或者比你小的数而且时间复杂度为O(N)
• 最后遍历输出最大值

3.代码展示

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        // 保存左右边界的值
        vector<int> left(n), right(n, n);

        stack<int> mono_stack;
        for(int i = 0; i < n; ++i)
        {
            while(!mono_stack.empty() && heights[mono_stack.top()] >= heights[i])
            {
                right[mono_stack.top()] = i;
                mono_stack.pop();
            }
            // 对于是升序的情况，就直接将栈顶作为哨兵
            // 降序的情况直接将i给top（这里的top一定是i的前一个位置），降序需要出栈
            left[i] = mono_stack.empty() ? -1 : 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;
    }
};