HDU3410 两边找最大 单调栈

题意

给定一个数列。

对于每一个，找两边的第一个比它大的值，然后在区间里找最大值，再在里找最大值。

思路

单调栈，再加一个判断。

Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
#define sc(x) scanf("%d", &(x))
#define me(L) memset(L, 0, sizeof(L))
int L[N], R[N], st[N], a[N];
int main() {
    int n, t, T;
    sc(T);
    for (int ca = 1; ca <= T; ++ca) {
        sc(n);
        for (int i = 1; i <= n; ++i) sc(a[i]);
        st[t = 0] = 0;
        for (int i = 1; i <= n; ++i) {
            int maxx = -1, k = 0;
            while (t && a[st[t]] < a[i]) {
                if (maxx < a[st[t]]) maxx = a[st[t]], k = st[t];
                --t;
            }
            L[i] = k;
            st[++t] = i;
        }
        st[t = 0] = n + 1;
        for (int i = n; i; --i) {
            int maxx = -1, k = 0;
            while (t && a[st[t]] < a[i]) {
                if (maxx < a[st[t]]) maxx = a[st[t]], k = st[t];
                --t;
            }
            R[i] = k;
            st[++t] = i;
        }
        printf("Case %d:\n", ca);
        for (int i = 1; i <= n; ++i) printf("%d %d\n", L[i], R[i]);
    }
    return 0;
}