一道非常好的单调栈的问题。

解题思路

对于每组数据我们维护一个单调栈,若栈顶元素小于当前元素,则弹栈并更新答案。
参考代码如下:

#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。
如果还对算法过程不理解可以造一个小数据手动模拟体会。

Last modification:March 5th, 2020 at 12:12 pm
博客维护不易,如果你觉得我的文章有用,请随意赞赏