JIAKAOBO

LeetCode

venmo
wechat

感谢赞助!

  • ㊗️
  • 大家
  • offer
  • 多多！

Problem

We are given a linked list with head as the first node. Let’s number the nodes in the list: node_1, node_2, node_3, … etc.

Each node may have a next larger value: for node_i, next_larger(node_i) is the node_j.val such that j > i, node_j.val > node_i.val, and j is the smallest possible choice. If such a j does not exist, the next larger value is 0.

Return an array of integers answer, where answer[i] = nextlarger(node{i+1}).

Note that in the example inputs (not outputs) below, arrays such as [2,1,5] represent the serialization of a linked list with a head node value of 2, second node value of 1, and third node value of 5.

Example 1:

Input: [2,1,5]
Output: [5,5,0]

Example 2:

Input: [2,7,4,3,5]
Output: [7,0,5,5,0]

Example 3:

Input: [1,7,5,1,9,2,5,1]
Output: [7,9,9,9,0,5,0,0]

Code

class Solution {
    class Node {
        int index;
        int val;
        public Node(int index, int val) {
            this.index = index;
            this.val = val;
        }
    }

    public int[] nextLargerNodes(ListNode head) {
        Stack<Node> stack = new Stack<>();
        List<Node> memo = new ArrayList<>();

        int index = 0;
        while(head != null) {
            int val = head.val;
            while(!stack.isEmpty() && val > stack.peek().val) {
                Node prev = stack.pop();
                memo.add(new Node(prev.index, val));
            }

            stack.push(new Node(index, val));
            index++;
            head = head.next;
        }

        int[] res = new int[index];
        for(Node curr : memo) {
            res[curr.index] = curr.val;
        }

        return res;
    }
}