题目

示例:
输入: [2,1,5,6,2,3]
输出: 10

解题代码与测试

//
// Created by tannzh on 2020/8/21.
//

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

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

    以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

    图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

    示例:

    输入: [2,1,5,6,2,3]
    输出: 10
 */

#include <vector>
#include <stack>
#include <algorithm>
#include <iostream>

using std::max;
using std::stack;
using std::vector;

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int max_area = 0, i = 0, size = heights.size();
        for (stack<int> stk; i<size || !stk.empty(); )
            if (stk.empty() || (i != size && heights[stk.top()] <= heights[i])) stk.push(i++);
            else {
                int tp = stk.top(); stk.pop();
                max_area = max(max_area, heights[tp] * (stk.empty() ? i : i-stk.top()-1));
            }
        return max_area;
    }
};

int main(int argc, char **argv)
{
    Solution s;
    std::vector<int> height{6, 2, 5, 4, 5, 1, 6};
    std::cout << s.largestRectangleArea(height);
}

解题思路分析

 _           _
| |  _   _  | |
| | | |_| | | |
| | |*|*|*| | |
| |_|*|*|*| | |
| | |*|*|*|_| |
|_|_|_|_|_|_|_|
 6 2 5 4 5 1 6
     ^ ^ ^
 0 1 2 3 4 5 6

如图所示，很直观：3 * 4 == 12.首先思考，我们是如何得到最大面积 12 的？

我们发现，要计算 Largest Rectangle ，关键是找短板，如我们挑选的 4，类似的还有哪些呢？列个表：

min_heightrectanglearea20 -> 42*542 -> 44*310 -> 61*6

最终很明显，area 最大的即为中间那行，结果为 12.

再进一步思考：

1. 短板是如何摘出来的？这个很显然，是衰减发生的时候出现的。如 6->2, 5->4, 5->1.
2. 短板的周期如何得出？细致观察后，发现是短板之间的升降分割出的。如 2->4:(2), 2->1, 4->1:(4), 2 和 4 便是分隔符。

好了，现在发现了规律，但如何准确找到所需的数据结构呢？

我们的第一个目的显然是要找出短板，短板的条件是：

height[i] < height[i-1]

貌似迭代一遍即可，但短板的周期分隔点如何得出呢？我们不仅要找出短板，还需要留下短板以及短板的 index, 以便寻找分隔符。

看来我们需要一把筛子，筛掉不符合短板条件的，留下短板。

栈非常符合筛子的特性，不管三七二十一，push 进去，不符合则 pop 出来。

int max_area = 0, i = 0, size = height.size();
for (stack<int> stk; i<size || !stk.empty(); ) { // 这个的 for 循环在二叉树的题目里经常出现（DFS）
    if (stk.empty() || (i != size && height[stk.top()] <= height[i])) stk.push(i++); // 不是短板，则 push
    else {
        int tp = stk.top(); stk.pop();
        max_area = std::max(max_area, height[tp] * (stk.empty() ? i : i-stk.top()-1));
    }
}

基本逻辑很简单，5 行结束。