题目描述
给出项数为 $n$ 的整数数列 $a_{1 \dots n}$。
定义函数 $f(i)$ 代表数列中第 $i$ 个元素之后第一个大于 $a_i$ 的元素的下标,即 $f(i)=\min_{i<j\leq n, a_j > a_i} {j}$。若不存在,则 $f(i)=0$。
试求出 $f(1\dots n)$。
输入格式
第一行一个正整数 $n$。
第二行 $n$ 个正整数 $a_{1\dots n}$。
输出格式
一行 $n$ 个整数表示 $f(1), f(2), \dots, f(n)$ 的值。
样例 #1
样例输入 #1
样例输出 #1
提示
【数据规模与约定】
对于 $30%$ 的数据,$n\leq 100$;
对于 $60%$ 的数据,$n\leq 5 \times 10^3$ ;
对于 $100%$ 的数据,$1 \le n\leq 3\times 10^6$,$1\leq a_i\leq 10^9$。
分析
一道纯模板题,单调栈 一般是处理当前 索引数值 右边或者左边 第一个比他 大或小 的值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92
| import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer;
public class P5788 {
static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int nextInt() throws IOException { st.nextToken(); return (int) st.nval; }
public static void main(String[] args) throws IOException { int n = nextInt();
int[] arr = new int[n + 1]; for (int i = 1; i <= n; i++) arr[i] = nextInt();
int[] f = new int[n + 1];
Stack stack = new Stack(n+1); for (int i = n; i >= 1; i--) { while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) { stack.poll(); } if (stack.isEmpty()) { f[i] = 0; } else { f[i] = stack.peek(); } stack.push(i); }
for (int i = 1; i <= n; i++) { System.out.print(f[i] + " "); } }
static class Stack { int[] arr;
int size = 0;
int index = -1;
Stack(int n) { arr = new int[n]; }
int getSize() { return size; }
boolean isEmpty(){ return getSize() == 0; }
void push(int val) { index++; arr[index] = val; size++; }
int peek() { return arr[index]; }
int poll() { int val = arr[index]; index--; size--; return val; }
}
}
|