题目描述
算法1
(暴力枚举) $O(n^2)$
C++ 代码
const int maxn = 1e5 + 10;
int n, h[maxn];
void solve(){
while(cin >> n, n){
rep(i, 1, n) read(h[i]);
int res = 0;
rep(i, 1, n){
int height = h[i];
// <---- 往左找第一个比height小的柱子
int left = 0, right = n+1;
repd(j, i, 1){
if(h[j] < height){
left = j;
break;
}
}
// ----> 往右找第一个比height小的柱子
rep(j, i, n){
if(h[j] < height){
right = j;
break;
}
}
res = max(res, (right - left - 1)*height);
}
cout << res << endl;
}
}
算法2
C++ 代码
const int maxn = 1e5 + 10;
int n, h[maxn];
void solve(){
while(cin >> n, n){
rep(i, 1, n) read(h[i]);
h[0] = h[n+1] = -1;
stack<int> s;
s.push(0);
int res = 0;
rep(i, 1, n + 1){
while(s.size() && h[s.top()] > h[i]){
int height = h[s.top()];
s.pop();
int left = s.top();
int right = i;
res = max(res, (right - left - 1)*height);
}
s.push(i);
}
cout << res << endl;
}
}
参考
https://www.acwing.com/solution/content/49961/