题目描述

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

解法一：暴力求解

主要思路是，遍历每个柱子，然后往柱子左右两边寻找比当前柱子矮的位置，从而计算出，以当前柱子为高度，所能围成的最大面积。 然后将这些面积中最大的值返回即可。暴力求解的时间复杂度为O(n^2)

不过我尝试过各种暴力求解，在 leetcode 中提交后都会超时。

class Solution {
public:
    int largestRectangleInHistogram(const std::vector<int>& inputs) {
        std::size_t n = inputs.size();
        int max_area = 0;
        for (int i = 0; i < n; ++i) {
            int min_height = INT_MAX;
            for (int j = i; j < n; ++j) {
                min_height = std::min(min_height, inputs[j]);
                max_area = std::max(max_area, min_height * (j - i + 1));
            }
        }
        return max_area;
    }
};

解法二：单调栈

class Solution {
public:
    int largestRectangleInHistogram(const std::vector<int>& inputs) {
        int n = inputs.size();
        std::stack<int> stk;
        int ret = 0;
        for (int i = 0; i < n; ++i) {
            while (!stk.empty() && inputs[stk.top()] > inputs[i]) {
                int w = i;
                int h = inputs[stk.top()];
                stk.pop();
                if (!stk.empty()) {
                    w = i - stk.top() - 1;
                }
                ret = std::max(ret, w * h);
            }
            stk.push(i);
        }
        while (!stk.empty()) {
            int w = n;
            int h = inputs[stk.top()];
            stk.pop();
            if (!stk.empty()) {
                w = n - stk.top() - 1;
            }
            ret = std::max(ret, w * h);
        }

        return ret;
    }
};