题解 | 直方图中最大矩形面积

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;

int T;
int n;

void solve(){
	
	cin>>n;
	vector<int> h(n+1);
	for(int i=0;i<n;i++){
		cin>>h[i];
	}
	
	stack<int> st;
	h.push_back(0);
	int max_area=0;
	
	for(int i=0;i<h.size();i++){
		while(!st.empty()&&h[i]<=h[st.top()]){
			int top_idx=st.top();
			st.pop();
			int height=h[top_idx];
			int width=st.empty()?i:(i-st.top()-1);
			max_area=max(width*height,max_area);
		}
		st.push(i);
		
	}
	
	cout<<max_area<<endl;
	
	return;
} 

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>T;
	
	while(T--){
		
		solve(); 
			
	}
	
	
    return 0;
}