CSP00 C题：最大的矩形

分析

对每一个柱子，高度记为$h$，需要找出它左侧（和右侧）第一个比它低的柱子的序号（分别记为$l,r$），这个柱子对应的最大矩形面积为$h(r-l-1)$。最终答案为所有柱子中最大的矩形面积。

题解

遍历

可以用$O(n^2)$的二重循环：遍历每个柱子，对每个柱子向左右各遍历一次找出第一个比当前柱子低的柱子。会超时。

单调栈

这种“向左/向右搜索第一个比当前大的数”问题，可以使用单调栈优化复杂度至$O(n)$：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
 
int main(){
	cerr.rdbuf(nullptr);
	ios::sync_with_stdio(false);cin.tie(nullptr);
	int n;
	cin>>n;
	vector<int> h(n+2);
	h[0]=0;h[n+1]=0;
	for(int i=1;i<=n;i++)cin>>h[i];
	stack<int> st;
	ll ans=0;
	for(int i=0;i<n+2;i++){
		while(!st.empty() && h[st.top()]>h[i]){
			int mid=st.top();
			st.pop();
			// 计算mid柱子对应的最大面积
			int width=i-st.top()-1,height=h[mid];
			// st.top() 是 mid 左边第一个比 h[mid] 矮的矩形条的下标。
			// i 就是 mid 右边第一个比它矮的矩形条的下标。
			ans=max(ans,(ll)width*height);
		}
		st.push(i);
	}
	cout<<ans;
}