1019. Next Grater Node in Linked List #

题目 #

给定一个长度为n的链表head

对于链表中的每个节点，查找下一个更大节点的值。即，对于每个节点，找到它旁边的第一个节点的值，这个节点的值严格大于它的值。

返回一个整数数组answer，其中answer[i]是第i个节点（从1开始）的下一个更大节点的值。如果第i个节点没有下一个更大的节点，设置answer[i] = 0。

思路 #

代码 #

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
    public int[] nextLargerNodes(ListNode head) {
        /** 1. 统计链表长度 */
        int length = 0;
        ListNode ptr = head;
        while (ptr != null) { length += 1; ptr = ptr.next; }
        
        /** 2. 将链表转化为数组 */
        int[] valueArray = new int[length];
        ptr = head;
        for (int i=0; i<length; i++) { valueArray[i] = ptr.val; ptr = ptr.next; }
        
        /** 3. 创建索引数组，存储当前元素下一个更大节点的下标值 */
        int[] indexArray = new int[length];
        
        /** 4. 创建结果数组，存储当前元素下一个更大节点的元素值 */
        int[] answer = new int[length];
        
        for (int i=length-1; i>=0; i--) {
            if (i == length-1) {
                indexArray[i] = -1;
                answer[i] = 0;
            } else if (valueArray[i] < valueArray[i+1]) {
                indexArray[i] = i+1;
                answer[i] = valueArray[i+1];
            } else {
                /** 当前节点不小于紧邻节点，借助索引数组寻找潜在的更大节点 */
                int index = indexArray[i+1];
                while (index != -1 && valueArray[i] >= valueArray[index]) index = indexArray[index];
                if (index == -1) {
                    indexArray[i] = -1;
                    answer[i] = 0;
                } else {
                    indexArray[i] = index;
                    answer[i] = valueArray[index];
                }
            }
        }
        return answer;
    }
}