链表中的下一个更大节点

发表于 分类于 阅读次数：

链表中的下一个更大节点（难度：中等）

1
2

方法：单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] nextLargerNodes(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        int[] arr = new int[10000];
        int[] arr2 = new int[10000];

        int length = 0;

        while(head != null){
            // 栈里存放索引
            arr2[length] = head.val;
            while(!stack.empty() && arr2[stack.peek()] < head.val){
                arr[stack.pop()] = head.val;
            }
            stack.push(length);
            head = head.next;
            length++;
        }

        int res[] = new int[length];
        for(int i = 0; i<length; i++){
            res[i] = arr[i];
        }
        return res;
    }
}
3