题解：P12241 [蓝桥杯 2023 国 C] 最大区间

· · 题解

题意简述

给定一个长度为 n 的序列，求最大的 (R - L + 1) \times \min(A_L, A_{L+1}, \ldots, A_R) 的值，就是区间长度乘以区间最小值的最大值。

算法思路

通过正向逆向两次单调栈扫描预处理，找出每个点作为区间最小点能获得的最大区间，很明显，区间越长越好。有一道极其相似的题：洛谷 P2422 良好的感觉。

  1. 确定左右边界：

    • 先初始化，初始化左端点为 0，右端点为 n+1。
    • 正向逆向跑一遍单调栈，求出每个点左边和右边第一个比 A_i 小的点的位置。
    • 此时 A_i 作为最小值的最大区间为 (l_i, r_i)，实际正确的区间长度为 r_i - l_i - 1，因为是以 A_i 为最小点的区间。
  2. 计算时注意： 区间不包含左右端点。

复杂度分析

代码实现

#include<cstdio>
#include<stack>
#include<climits>
#include<algorithm>

using namespace std;

typedef long long ll;

const ll maxn = 3e5 + 5;

ll n, num[maxn];
void Input() {
    scanf("%lld", &n);
    for (ll i = 1; i <= n; ++i) {
        scanf("%lld", &num[i]);
    }
}

ll l[maxn], r[maxn];
void Init() {
    for (ll i = 1; i <= n; ++i) {
        l[i] = 0;
        r[i] = n + 1;
    }
}

stack<ll> s;
ll ans = INT_MIN;
void Sol() {
    for (ll i = 1; i <= n; ++i) {
        while (!s.empty() && num[s.top()] > num[i]) {
            r[s.top()] = i;
            s.pop();
        }
        s.push(i);
    }
    while (!s.empty()) {
        s.pop();
    }
    for (ll i = n; i >= 1; --i) {
        while (!s.empty() && num[s.top()] > num[i]) {
            l[s.top()] = i;
            s.pop();
        }
        s.push(i);
    }
    for (ll i = 1; i <= n; ++i) {
        ans = max(ans, ((r[i] - 1) - (l[i] + 1) + 1) * num[i]);
    }
}

int main() {
    Input();
    Init();
    Sol();
    printf("%lld", ans);
    return 0;
}

注意：初始化时左右边界分别为 0 和 n+1。