链表中的下一个更大节点【LC1019】
给定一个长度为
n的链表head对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。返回一个整数数组
answer，其中answer[i]是第i个节点( 从1开始 )的下一个更大的节点的值。如果第i个节点没有下一个更大的节点，设置answer[i] = 0。
好久没做单调栈啦
- 思路
首先遍历一遍链表，将链表中的元素存储在集合中，然后使用单调递减栈找到严格大于在栈顶元素的下一个元素，当当前元素大于栈顶元素时，将栈顶元素弹出，并记录结果，因此栈中需要记录二元组{下标,值} - 实现
class Solution { public int[] nextLargerNodes(ListNode head) { ListNode cur = head; List<Integer> nums = new ArrayList<>(); while (cur != null){ nums.add(cur.val); cur = cur.next; } int n = nums.size(); Deque<int[]> st = new LinkedList<>(); int[] res = new int[n]; for (int i = 0; i < n; i++){ while (!st.isEmpty() && st.peekLast()[1] < nums.get(i)){ res[st.pollLast()[0]] = nums.get(i); } st.addLast(new int[]{i, nums.get(i)}); } return res; } }
