找山坡
时间限制：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; }
