输出索引并采用哨兵的方式处理边界
左边第一个大的
Stack<Integer> stk = new Stack<>();
stk.push(0);
a[0] = INF;
for (int i = 1; i <= n; i++) {
while (!stk.isEmpty() && a[stk.peek()] <= a[i]) stk.pop();
if (stk.peek() == 0) out.print(-1 + " ");
else out.print(stk.peek() + " ");
stk.push(i);
}
左边第一个小的
Stack<Integer> stk = new Stack<>();
stk.push(0);
a[0] = -INF;
for (int i = 1; i <= n; i++) {
while (!stk.isEmpty() && a[stk.peek()] >= a[i]) stk.pop();
if (stk.peek() == 0) out.print(-1 + " ");
else out.print(stk.peek() + " ");
stk.push(i);
}
相比单调队列
单调队列对头是最值
例如:要求窗口最小值,就需要维护对头最小,也就是单调递增队列是
while(!q.isEmpty() && a[q.getLast] >= a[i]) q.removeLast();
q.addLast(i);
min = q.getFirst();
单调栈栈顶是第一个符合条件的值
例如:要求左边第一个小的值的索引
while (!stk.isEmpty() && a[stk.peek()] >= a[i]) a.pop();
if (stk.isEmpty()) ans = 0;
else ans = stk.peek();
a.push(i);