2021年广东工业大学第十五届文远知行杯程序设计竞赛（同步赛）B.找山坡

题目链接

题目描述

母牛哥在电脑面前坐久了，想站起来看看窗外的小山坡，于是就想出了这个问题：
给定一个大小为 n 的数组 a，序号从 1 开始，
计算:

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

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

输入描述

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

输出描述

输出题目所求的值

示例1

输入

5
1 2 3 2 1

输出

4

单调栈~
单调栈里元素值递增，当当前元素小于栈顶元素时，一直弹出栈顶即可，直到出现以下三种情况：

• 栈为空，此时直接压入元素即可
• 栈顶元素等于当前元素，将两者下标之差和答案取 max
• 栈顶元素小于当前元素，压入元素即可

AC代码如下：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

int n, ans, a[1000005];

int main() {
    cin >> n;
    stack<int> s;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        while (!s.empty() && a[i] < a[s.top()]) s.pop();
        if (s.empty()) s.push(i);
        else if (a[i] == a[s.top()]) ans = max(ans, i - s.top());
        else s.push(i);
    }
    cout << ans;
    return 0;
}