洛谷 P4273. 最大的矩形纸片

题目描述

link

分析

略

代码实现

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6 + 10;
int n, ans, h[N], l[N], r[N], s[N], top;

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];

    for (int i = 1; i <= n; i++) {
        while (top && h[i] <= h[s[top]]) --top;
        if (top) l[i] = s[top];
        else l[i] = 0;
        s[++top] = i;
    }

    top = 0;
    for (int i = n; i >= 1; i--) {
        while (top && h[i] <= h[s[top]]) --top;
        if (top) r[i] = s[top];
        else r[i] = n + 1;
        s[++top] = i;
    }

    for (int i = 1; i <= n; i++) {
        ans = max(ans, (r[i] - l[i] - 1) * h[i]);
    }
    cout << ans << endl;

    return 0;
}

精简版本：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6 + 10;
int n, ans, h[N], st[N], top;

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];
    h[0] = h[n + 1] = 0;

    top = 0, ans = 0;
    st[++top] = h[0];
    for (int i = 1; i <= n + 1; i++) {
        while (h[st[top]] > h[i]) {
            int height = h[st[top--]];
            int width = i - st[top] - 1;
            ans = max(ans, width * height);
        }
        st[++top] = i;
    }
    cout << ans << endl;

    return 0;
}