题目链接：Largest Rectangle in a Histogram (nowcoder.com)

题目难度3星，做法比较多，稍微优化一下的暴力枚举也能过，这里写一下单调栈的做法。

题目大意

给一个类似条形统计图的东西，每个点有各自的高度，求可以从中截取的最大矩形面积。

思路

有可能是最大矩形的矩形其实就是各个点的高度，向左右延伸最长距离得到的。

那么就遍历每个点，向左右延伸，直到遇到比该点更小的点就停止。

不难发现，这又是有方向的遍历且有明确的大小关系，所以考虑用单调栈，之前这道题《[USACO 2006 Nov S]Bad Hair Day（单调栈） – ErikTse Runtime》也用了单调栈。

代码

/* Copyright (C) 2022 ErikTse */
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <utility>
#include <stack>
#include <algorithm>
#define pb push_back
#define fi first
#define se second
#define pr printf
#define sc scanf
#define gc getchar
#define int long long
//请使用%lld输出long long类型数据
using namespace std;
inline int re(){
	int s = 0,w = 1;char c = gc();
	while(c > '9' || c < '0'){if(c == '-')w = -1;c = gc();}
	while('0' <= c && c <= '9'){s = s * 10 + c - '0',c = gc();}
	return s * w;
}
/*-------全局变量------*/
typedef pair<int, int> PII;
const int maxn = 1e5 + 10;
int h[maxn];//存高度 
int sq[maxn];//存下该点向左右延伸的最大面积 
PII stk[maxn];//{位置，高度}
int N, top = 0;


/*-----自定义函数------*/
inline void solve()
{
	for(int i = 1;i <= N; ++ i)h[i] = re();
	h[N + 1] = 0;//最后一个设置为 0 是为了将所有元素都出栈算出可能的面积 
	top = 0;
	memset(sq, 0, sizeof sq);
	//其实这里高度可以不用存储 
	for(int i = 1;i <= N + 1; ++ i)
	{
		while(top && stk[top].se >= h[i])//如果h[i] <= 栈顶高度，说明栈顶元素右边边界就是 i 
		{
			sq[stk[top].fi] += (i - stk[top].fi) * stk[top].se;//注意算面积左闭右开 
			top --;
		}
		sq[i] += (i - stk[top].fi - 1) * h[i];//因为是单调递增栈，所以 i 左边界就是栈顶 
		stk[++ top] = {i, h[i]};//入栈 
	}
	int ans = 0;
	for(int i = 1;i <= N; ++ i)ans = max(ans, sq[i]);
	pr("%lld\n",ans);
	return;
}

signed main()
{
	//freopen("in.txt","r",stdin);
	while(cin >> N && N != 0)solve();
	return 0;
}