题目来源

1019. 链表中的下一个更大节点

题目描述

题目解析

这题考单调栈

而所谓 单调栈 则是在栈的 先进后出 基础之上额外添加一个特性：从栈顶到栈底的元素是严格递增（or递减）。

具体进栈过程如下：

对于单调递增栈，若当前进栈元素为 e，从栈顶开始遍历元素，把小于 e 或者等于 e 的元素弹出栈，直接遇到一个大于 e 的元素或者栈为空为止，然后再把 e 压入栈中。对于单调递减栈，则每次弹出的是大于 e 或者等于 e 的元素

例子 以 单调递增栈 为例进行说明。

现在有一组数

3，4，2，6，4，5，2，3 让它们从左到右依次入栈。

具体过程如下：

public static int[] nextLargerNodes(ListNode head) { ArrayList<Integer> list = new ArrayList<>(); while (head != null){ list.add(head.val); head = head.next; } int [] res = new int[list.size()]; // 栈压入两个东西： 当前值的索引 | 当前值 | 当前值的索引 | 当前值 Stack<Integer> stack = new Stack<>(); for (int i = 0; i < list.size(); i++){ int cur = list.get(i); while (!stack.empty() && cur > stack.peek() ){ // 需要淘汰比他小的 stack.pop(); res[stack.pop()] = cur; } stack.push(i); stack.push(cur); } return res; }