第十四届蓝桥杯省赛真题——最大区间（AC）

1. 异或和

• 前置知识点：单调栈。
• 相似题目：好子数组的最大得分

1. 问题描述

给定一个长度为 $n$ 的序列 $A_i$，求 $L,R$ 使 $(R?L+1)?\min (A_L,A_{L+1},\dots ,A_R)$ 尽可能大，其中 $\min$ 表示最小值。

你只需要输出最大的值即可，不需要输出具体的 $L,R$。

2. 输入格式

输入的第一行包含一个整数 $n$。

第二行包含 $n$ 个整数，分别表示 $A_1,A_2,\dots ,A_n$，相邻两个整数之间使用一个空格分隔。

3. 输出格式

输出一行包含一个整数表示答案。

4. 样例输入

5
1 1 3 3 1

5. 样例输出

6

6. 评测用例规模与约定

对于 $40\%$ 的评测用例，$1\le n\le 5000$，$1\le A_i\le 5000$；

对于所有评测用例，$1\le n\le 3\times 10^5$，$1\le A_i\le 10^9$。

7. 原题链接

最大区间

2. 解题思路

这个问题要求我们找到 $\underset{1\le L\le R\le n}{\max }\{(R?L+1)\times \min (A_L,A_{L+1},?A_R)\}$。

简单的想法是，枚举所有的区间 $[L,R](1\le L\le R)$ 并计算它们的值，但因为区间的总个数是 $O(n^2)$ 级别，这个方法的时间复杂度过高。

我们仔细来观察这个式子：
$$(R?L+1)\times \min (A_L,A_{L+1},?A_R)$$
它是由两部分构成 —— $(R?L+1)$ 和 $\min (A_L,A_{L+1},?A_R)$。我们前面考虑的做法是枚举前半部分，发现区间个数的数量级太大。

我们可以尝试另一种策略，即枚举后半部分 $\min (A_L,A_{L+1},?A_R)$。

首先能明确一点的是，枚举后半部分的复杂度肯定是 $O(n)$ 级别的，因为数组中只有 $n$ 个数，我们枚举每个数作为区间最小值，显然复杂度是 $O(n)$ 级别。

真正的核心点在于当我们确定某个点 $i(i\in [1,n])$ 作为区间最小值，即式子右半部分的值。我们如何去确定 $L,R$ 呢？

从贪心的角度考虑，我们肯定是希望 $R?L+1$ 越大越好，即希望 $L$ 尽可能地小并且 $R$ 尽可能地大。

有的人可能会想，那我 $L$ 就取 $1$，$R$ 就取 $n$ 不就好了？显然此时忽略了一个问题 —— $A_i$ 必须是区间 $[L,R]$ 的最小值。

$A_i$ 作为区间最小值是我们选择它的前提，我们不能违背。即我们需要找到最小的 $L$ 和最大的 $R$ 并且使得 $[L,R]$ 不能出现比 $A_i$ 还小的元素。

这个问题等价于寻找 $A_i$ 上一个比它小的元素和下一个比它大的元素，这是数据结构中单调栈的经典应用。

• 单调栈简介：

单调栈是一种特殊的栈结构，它的主要特性是在栈内部，元素按照一种单调递增或递减的顺序排列。这种单调性可以根据实际问题的需要来确定。使用单调栈，我们可以在 $O(n)$ 的时间复杂度内解决一些看似复杂的问题。

主要应用

单调栈最常见的应用是解决 “下(上)一个更大元素” 或 “下(上)一个更小元素” 的问题。具体来说，给定一个数组，我们可能想要找到对于每个位置，其右边第一个比它大（或小）的元素。通过维护一个单调栈，我们可以在遍历数组的过程中，对于每个元素，都在常数时间内找到其对应的元素。

工作原理

在构造单调递减栈时，我们从左到右遍历数组，对于每个元素，如果栈为空或者该元素小于或等于栈顶元素，我们就将其压入栈中；否则，我们就不断从栈中弹出元素，直到栈为空或者找到一个栈顶元素小于当前元素，然后再将当前元素压入栈中。这样，我们就可以保证栈内元素的单调性。

单调递增栈的构造与此类似，只是条件相反。

通过这种方式，我们可以保证对于栈中的每个元素，其在数组中的下一个更大（或更小）元素就是首次导致其被弹出栈的那个元素。

想更详细地学习单调栈可见：https://oi-wiki.org/ds/monotonous-stack/。

根据上述分析，我们只需要先使用单调栈在 $O(n)$ 的复杂度预处理得到每个元素 $A_i$ 上一个比它小的元素位置和下一个比它小的元素位置，我们设为 $l_i$ 和 $r_i$，然后枚举每个数作为区间最小值，可计算出它的值为：
$$(r[i]?l[i]?1)\times A_i$$
我们只需要取一个最大的值作为答案即可，在计算时注意答案可能超出 int 的取值范围。

时间复杂度：$O(n)$。

3. AC_Code

• C++

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int n;
void solve() {
    int n;
    cin >> n;

    vector<LL> a(n), l(n, -1), r(n, n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    deque<int> s;
    for (int i = 0; i < n; ++i) {
        while (s.size() && a[s.back()] >= a[i]) {
            s.pop_back();
        }
        if (s.size())
            l[i] = s.back();

        s.push_back(i);
    }

    s.clear();
    for (int i = n - 1; i >= 0; --i) {
        while (s.size() && a[s.back()] >= a[i]) {
            s.pop_back();
        }
        if (s.size())
            r[i] = s.back();
        s.push_back(i);
    }
    LL ans = 0;
    for (int i = 0; i < n; ++i) {
        ans = max(ans, 1LL * (r[i] - l[i] - 1) * a[i]);
    }

    cout << ans << '\n';
}
int main() {
    ios_base ::sync_with_stdio(false);
    cin.tie(0);
    cout << setiosflags(ios::fixed) << setprecision(2);
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}

• Java

import java.io.*;
import java.util.*;

public class Main {
    
    public static void main(String[] args) {
        FastReader reader = new FastReader();
        int t = 1;
        while (t-- > 0) {
            solve(reader);
        }
    }
    
    public static void solve(FastReader reader) {
        int n = reader.nextInt();

        long[] a = new long[n];
        int[] l = new int[n];
        int[] r = new int[n];
        Arrays.fill(l, -1);
        Arrays.fill(r, n);

        for (int i = 0; i < n; ++i) {
            a[i] = reader.nextLong();
        }

        Deque<Integer> s = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) {
            while (!s.isEmpty() && a[s.peekLast()] >= a[i]) {
                s.pollLast();
            }
            if (!s.isEmpty())
                l[i] = s.peekLast();

            s.addLast(i);
        }

        s.clear();
        for (int i = n - 1; i >= 0; --i) {
            while (!s.isEmpty() && a[s.peekLast()] >= a[i]) {
                s.pollLast();
            }
            if (!s.isEmpty())
                r[i] = s.peekLast();
            s.addLast(i);
        }
        long ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, 1L * (r[i] - l[i] - 1) * a[i]);
        }

        System.out.println(ans);
    }

    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;

        public FastReader()
        {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() { return Integer.parseInt(next()); }

        long nextLong() { return Long.parseLong(next()); }
    }
}

• Python

def solve():
    n = int(input())
    a = list(map(int, input().split()))

    l = [-1] * n
    r = [n] * n

    s = []
    for i in range(n):
        while s and a[s[-1]] >= a[i]:
            s.pop()
        if s:
            l[i] = s[-1]
        s.append(i)

    s.clear()
    for i in range(n - 1, -1, -1):
        while s and a[s[-1]] >= a[i]:
            s.pop()
        if s:
            r[i] = s[-1]
        s.append(i)

    ans = 0
    for i in range(n):
        ans = max(ans, (r[i] - l[i] - 1) * a[i])

    print(ans)


if __name__ == "__main__":
    t = 1
    while t > 0:
        solve()
        t -= 1