题目链接

算法竞赛进阶指南-45.直方图中最大的矩形

直方图是由在公共基线处对齐的一系列矩形组成的多边形。

矩形具有相等的宽度，但可以具有不同的高度。

例如，图例左侧显示了由高度为 $2,1,4,5,1,3,3$ 的矩形组成的直方图，矩形的宽度都为 $1$：

通常，直方图用于表示离散分布，例如，文本中字符的频率。

现在，请你计算在公共基线处对齐的直方图中最大矩形的面积。

图例右图显示了所描绘直方图的最大对齐矩形。

输入格式

输入包含几个测试用例。

每个测试用例占据一行，用以描述一个直方图，并以整数 $n$ 开始，表示组成直方图的矩形数目。

然后跟随 $n$ 个整数 $h_1，…，h_n$。

这些数字以从左到右的顺序表示直方图的各个矩形的高度。

每个矩形的宽度为 $1$。

同行数字用空格隔开。

当输入用例为 $n=0$ 时，结束输入，且该用例不用考虑。

输出格式

对于每一个测试用例，输出一个整数，代表指定直方图中最大矩形的区域面积。

每个数据占一行。

请注意，此矩形必须在公共基线处对齐。

数据范围

$1 \le n \le 100000$,
$0 \le h_i \le 1000000000$

输入样例：

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

输出样例：

8
4000

Method : 单调栈

根据题意，需要构造一个单峰/\（中间高两边低）才能计算出$cur$矩形的最大面积，因此可以构造一个严格单调递增的单调栈来完成这个操作，并且对于当前的每个谷峰$cur$，其能形成的最大矩形面积$S_{area}$为：

$S_{area} = w * h = (r - l - 1) * height[cur]$

如果没有形成单峰"/\，其实当前单个上升区间/也能计算矩形面积，那么就有必要把遍历完后留在单调栈中的数全部弹出来算一次，但这样会导致代码冗余（逻辑重复），因此可以添加一个尾部哨兵来统一操作。

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

using namespace std;

typedef long long LL;

vector<int> height;
stack<int> S;

int main() {
    int n;
    while (scanf("%d", &n), n) {
        height.resize(n);
        
        for (int i = 0; i < n; i ++) {
            scanf("%d", &height[i]);
        }
        
        height.push_back(0);       // 尾部哨兵
        n = height.size();

        LL res = 0;
        S = stack<int>();
        for (int i = 0; i < n; i ++) {
            while (!S.empty() && height[S.top()] >= height[i]) {
                int cur = S.top();
                S.pop();
                int r = i;  
                int l = S.empty() ? -1 : S.top();
                res = max(res, (r - l - 1) * (LL)height[cur]);
            }
            S.push(i);
        }       
        
        cout << res << endl;
    }
    
    return 0;
}

复杂度分析

• 时间复杂度：${O(n)}$， 对于数组中的每个元素，最多只会进出栈一次。

• 空间复杂度：${O(n)}$。

另一种写法，但是感觉有些麻烦，仅供参考：

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

using namespace std;

typedef long long LL;

const int N = 1e5 + 7;

vector<int> height(N);
vector<int> l(N);
vector<int> r(N);
stack<int> stk;

int main() {
    int n;
    while (scanf("%d", &n), n) {
        for (int i = 0; i < n; i ++) {
            scanf("%d", &height[i]);
        }
        
        // left
        stk = stack<int>();
        for (int i = 0 ; i < n; i ++) {
            while(!stk.empty() && height[stk.top()] >= height[i]) {
                stk.pop();
            }
            l[i] = stk.empty() ? -1 : stk.top();
            stk.push(i);
        }
        
        // right
        stk = stack<int>();
        for (int i = n - 1; i >= 0; i --) {
            while(!stk.empty() && height[stk.top()] >= height[i]) {
                stk.pop();
            }
            r[i] = stk.empty() ? n : stk.top();
            stk.push(i);
        }
        
        LL res = 0;
        for (int i = 0; i < n; i ++) {
            LL cur = (LL)height[i] * (r[i] - l[i] - 1);
            res = max(res, cur);
        }
        
        cout << res << endl;
    }
    
    
    return 0;
}