小b有一个长度为 n 的序列 t,现在她对于每个 i,求最小的正数 j 满足 i+j <= n 且 t[i+j] > t[i],输出 j,如果不存在这样的 j,则输出 0。
第一行输入一个数 n;
第二行输入 n 个数 t1-tn,以空格隔开;
其中 1 <= n <= 30000,对于任意 t[i] 满足 30 <= t[i] <= 100。
输出一行 n 个数,第 i 个数表示 i 的答案。
8 73 74 75 71 69 72 76 73
1 1 4 2 1 1 0 0
从右往左扫描,维护一个单调递减的栈(栈中保存下标,越靠近栈顶的值越小)。插入当前位置 i 前,不断弹出栈中值小于等于 t[i] 的下标,此时栈顶就是 i 后面第一个比它大的位置,答案即栈顶下标减 i;栈空则答案为 0。总复杂度 O(n)。