2021年广工大第十五届文远知行杯-B找山坡-栈

找山坡

时间限制：C/C++ 3秒，其他语言6秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

母牛哥在电脑面前坐久了，想站起来看看窗外的小山坡，于是就想出了这个问题：

给定一个大小为n的 数组 a，序号从1开始，

计算:

max{ R - L | 1 <= L <= R <= n, a[L] == a[R], 对于所有i (L <= i <= R), 满足a[i] >= a[L] }.

也就是找到两个坐标,这两个坐标的值相等,并且他们之间的值都大于等于这两个坐标上的值.

这两个坐标相减最大能是多少.

输入描述:

第一行一个整数n，第二行n个整数

输出描述:

输入

5
1 2 3 2 1

输出

4

说明

当L=1，R=5时，满足题目条件的最优解，答案为R-L=5-1=4

备注:

数据范围：

1 <= n <= 1e6

0 <= a[i] <= 1e9

当时看到很多巨巨用RMQ or 线段树来操作

现在用单调栈来操作一下

在栈中，我们放进去的是数的下标

根据题意可以知道：当前的数大于栈顶的元素的情况下，我们可以将这个数放进去，因为此时这个数可能会对后面的数产生贡献，但如果当前这个数小于栈顶元素，我们就要将栈顶元素往外pop();

当栈空了的时候就将当前这个数的下标push()进去

当栈顶元素值等于当前值大小，这个时候就要算贡献了，此时对答案的贡献就是MAX{ans,i-top()}

要是经过一番判断仍不相等，放进去当前下标就好了

const int maxn = 1e6 + 7;
int n;
int a[maxn];
stack<int> st;
int main(){
    cin >> n;
    int ans = 0;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        while(st.size() && a[st.top()] > a[i]) st.pop();
        if(st.empty()) st.push(i);
        else if(a[st.top()] == a[i]) ans = max(ans,i-st.top());
        else st.push(i);
    }
    cout<<ans;
    return 0;
}