一道非常好的单调栈的问题。
解题思路
对于每组数据我们维护一个单调栈,若栈顶元素小于当前元素,则弹栈并更新答案。
参考代码如下:
#include <bits/stdc++.h>
#define MAXN 100001
using namespace std;
using ll = long long;
int n;
int data[MAXN];
int w[MAXN];
stack<int> s;
ll ans;
int main() {
ios::sync_with_stdio(false);
while(cin >> n && n) {
for(int i = 0; i < n; ++i)
cin >> data[i];
data[n] = -1;
for(int i = 0; i <= n; ++i) {
int width = 0;
if(!s.empty() && data[i] < data[s.top()]) {
while(!s.empty() && data[i] < data[s.top()]) {
width += w[s.top()];
ans = max(ans,(ll) width * data[s.top()]);
s.pop();
}
}
s.push(i);
w[i] = width + 1;
}
cout << ans << endl;
ans = 0;
s.pop();
}
return 0;
}
这里说明几个细节,在最后一个数据后我们添加一个高度为-1的矩形,目的是偷懒将栈清空更新答案。
width变量记录被弹出矩形宽度之和。w数组储存之前被弹出矩形宽度之和,若没被弹出则初始化为1。
如果还对算法过程不理解可以造一个小数据手动模拟体会。