1019. Next Greater Node In Linked List

class Solution {
    private static class Pair {
        ListNode node;
        int idx;

        Pair(ListNode _node, int _idx) {
            node = _node;
            idx = _idx;
        }
    }

    public int[] nextLargerNodes(ListNode head) {
        Stack<Pair> stack = new Stack<>();
        ListNode ptr = head;

        // Get the list size
        int listSize = 0;
        while (ptr != null) {
            listSize += 1;
            ptr = ptr.next;
        }

        int[] ans = new int[listSize];
        int idx = 0;
        ptr = head;
        while (ptr != null) {
            while (!stack.isEmpty() && ptr.val > stack.peek().node.val) {
                ans[stack.pop().idx] = ptr.val;
            }
            stack.push(new Pair(ptr, idx));
            idx += 1;
            ptr = ptr.next;
        }
        return ans;
    }
}

经典的monotonic stack的使用场景. 只不过和链表组合在一起了.

时间复杂度: O(n)
空间复杂度: O(n)