第十五届蓝桥杯省赛第二场C/C++B组G题【最强小队】题解

20pts

枚举所有可能的左端点、右端点，时间复杂度 $O(n^2)$。

对于每个区间进行遍历检测，时间复杂度 $O(n^3)$。

100pts

由于数据范围为 $10^5$，所以肯定只能进行一次枚举。

我们尝试枚举右端点，当一个点作为右端点时，那么，该点可能是最大值，也可能是次大值，较难实现。

尝试枚举每个点作为次大值点，那么，若 $a[x]$ 作为次大值点，我们需要做的就是，找出左侧的第一个 $\ge a[x]$ 的点，假设坐标为 $y$，那么他俩一定可以构成一个区间，区间大小为 $x-y+1$。

同理，可以找出右侧第一个 $\ge a[x]$ 的点，假设坐标为 $y$，那么区间大小为 $y-x+1$。

此处，我们可以使用单调栈进行查找左侧第一个大于自己的下标，以及右侧第一个大于自己的下标。

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

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <stack>

using namespace std;

const int N = 1e5 + 10;

int n;
int a[N];
int lef[N], rig[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    for (int i = 1; i <= n; ++ i )
        cin >> a[i];
    
    a[0] = a[n + 1] = 2e9;
    
    stack<int> stk;
    stk.push(0);
    for (int i = 1; i <= n; ++ i )
    {
        while (a[stk.top()] < a[i])
            stk.pop();
        lef[i] = stk.top();
        stk.push(i);
    }
    
    while (stk.size())
        stk.pop();
    stk.push(n + 1);
    for (int i = n; i; -- i )
    {
        while (a[stk.top()] < a[i])
            stk.pop();
        rig[i] = stk.top();
        stk.push(i);
    }
    
    int res = 0;
    for (int i = 1; i <= n; ++ i )
    {
        if (lef[i] != 0)
            res = max(res, i - lef[i] + 1);
        if (rig[i] != n + 1)
            res = max(res, rig[i] - i + 1);
    }
    
    cout << res << endl;
    
    return 0;
}