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

心已赠人 2024-04-20 11:40 6阅读 0赞

#### 目录 ####

*  1. 最大区间
 *   *  1. 问题描述
     *  2. 输入格式
     *  3. 输出格式
     *  4. 样例输入
     *  5. 样例输出
     *  6. 评测用例规模与约定
     *  7. 原题链接
 *  2. 解题思路
 *  3. AC\_Code

## 1. 最大区间 ##

*  前置知识点：单调栈。
 *  相似题目：[好子数组的最大得分][Link 1]

### 1. 问题描述 ###

给定一个长度为  n n n 的序列  A i A\_i Ai，求  L , R L,R L,R 使  ( R − L + 1 ) ⋅ min ⁡ ( A L , A L + 1 , … , A R ) (R - L + 1) \\cdot \\min(A\_L, A\_\{L+1\}, \\ldots, A\_R) (R−L\+1)⋅min(AL,AL\+1,…,AR) 尽可能大，其中  min ⁡ \\min min 表示最小值。

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

### 2. 输入格式 ###

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

第二行包含  n n n 个整数，分别表示  A 1 , A 2 , … , A n A\_1, A\_2, \\ldots, A\_n A1,A2,…,An，相邻两个整数之间使用一个空格分隔。

### 3. 输出格式 ###

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

### 4. 样例输入 ###

5
    1 1 3 3 1

### 5. 样例输出 ###

### 6. 评测用例规模与约定 ###

对于  40 % 40\\% 40% 的评测用例， 1 ≤ n ≤ 5000 1 \\leq n \\leq 5000 1≤n≤5000， 1 ≤ A i ≤ 5000 1 \\leq A\_i \\leq 5000 1≤Ai≤5000；

对于所有评测用例， 1 ≤ n ≤ 3 × 1 0 5 1 \\leq n \\leq 3 \\times 10^5 1≤n≤3×105， 1 ≤ A i ≤ 1 0 9 1 \\leq A\_i \\leq 10^9 1≤Ai≤109。

### 7. 原题链接 ###

[最大区间][Link 2]

## 2. 解题思路 ##

这个问题要求我们找到  max ⁡ 1 ≤ L ≤ R ≤ n \{ ( R − L + 1 ) × min ⁡ ( A L , A L + 1 , ⋯ A R ) \} \\underset\{1 \\leq L \\leq R \\leq n\}\{\\max\} \\lbrace(R-L+1) \\times \\min(A\_L,A\_\{L+1\}, \\cdots A\_R) \\rbrace 1≤L≤R≤nmax\{(R−L\+1)×min(AL,AL\+1,⋯AR)\}。

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

我们仔细来观察这个式子：  
 ( R − L + 1 ) × min ⁡ ( A L , A L + 1 , ⋯ A R ) (R-L+1) \\times \\min(A\_L,A\_\{L+1\}, \\cdots A\_R) (R−L\+1)×min(AL,AL\+1,⋯AR)  
它是由两部分构成 ——  ( R − L + 1 ) (R-L+1) (R−L\+1) 和  min ⁡ ( A L , A L + 1 , ⋯ A R ) \\min(A\_L,A\_\{L+1\}, \\cdots A\_R) min(AL,AL\+1,⋯AR)。我们前面考虑的做法是枚举前半部分，发现区间个数的数量级太大。

我们可以尝试另一种策略，即枚举后半部分  min ⁡ ( A L , A L + 1 , ⋯ A R ) \\min(A\_L,A\_\{L+1\}, \\cdots A\_R) min(AL,AL\+1,⋯AR)。

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

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

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

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

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

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

*  单调栈简介：

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

**主要应用**

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

**工作原理**

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

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

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

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

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

时间复杂度： O ( n ) O(n) 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

[Link 1]: https://leetcode.cn/problems/maximum-score-of-a-good-subarray/description/
[Link 2]: https://www.lanqiao.cn/problems/6232/learning/