单调栈，对于每根柱子，分别向左右遍历，用单调栈预处理出来第$i$个柱子左边第一个比它矮的柱子的位置($l[i]$）和右边第一个比它矮的柱子的位置$r[i]$， 那么以第$i$根柱子为最矮高度时，可形成的最大宽度是

对应的面积即:

遍历一遍取个最大值即可。

时间复杂度：$O(T \times n)$

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#define endl '\n'
using namespace std;
using LL = long long;

void solve(){
	int n;
	cin >> n;
	vector<int> h(n);
	for(int i = 0; i < n; i++){
		cin >> h[i];
	}
	vector<int> l(n), r(n);
	stack<int> stk;
	while(!stk.empty()) stk.pop();
	for(int i = 0; i < n; i++){
		while(!stk.empty() && h[stk.top()] >= h[i]){
			stk.pop();
		}
		l[i] = stk.empty() ? -1 : stk.top();
		stk.push(i);
	}
	while(!stk.empty()) stk.pop();
	for(int i = n - 1; i >= 0; i--){
		while(!stk.empty() && h[stk.top()] >= h[i]){
			stk.pop();
		}
		r[i] = stk.empty() ? n : stk.top();
		stk.push(i);
	}
	LL res = 0;
	for(int i = 0; i < n; i++){
		LL width = r[i] - l[i] - 1;
		res = max(res, (LL)h[i] * width);
	}
	cout << res << endl;
}

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