题目描述

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

解法一：暴力求解

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

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

 1class Solution {
 2public:
 3    int largestRectangleInHistogram(const std::vector<int>& inputs) {
 4        std::size_t n = inputs.size();
 5        int max_area = 0;
 6        for (int i = 0; i < n; ++i) {
 7            int min_height = INT_MAX;
 8            for (int j = i; j < n; ++j) {
 9                min_height = std::min(min_height, inputs[j]);
10                max_area = std::max(max_area, min_height * (j - i + 1));
11            }
12        }
13        return max_area;
14    }
15};

解法二：单调栈

 1class Solution {
 2public:
 3    int largestRectangleInHistogram(const std::vector<int>& inputs) {
 4        int n = inputs.size();
 5        std::stack<int> stk;
 6        int ret = 0;
 7        for (int i = 0; i < n; ++i) {
 8            while (!stk.empty() && inputs[stk.top()] > inputs[i]) {
 9                int w = i;
10                int h = inputs[stk.top()];
11                stk.pop();
12                if (!stk.empty()) {
13                    w = i - stk.top() - 1;
14                }
15                ret = std::max(ret, w * h);
16            }
17            stk.push(i);
18        }
19        while (!stk.empty()) {
20            int w = n;
21            int h = inputs[stk.top()];
22            stk.pop();
23            if (!stk.empty()) {
24                w = n - stk.top() - 1;
25            }
26            ret = std::max(ret, w * h);
27        }
28
29        return ret;
30    }
31};