1019. 链表中的下一个更大节点.md

1019. 链表中的下一个更大节点

• 栈(基础版)

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
type Index = number;
type Value = number;
function nextLargerNodes(head: ListNode | null): number[] {

    const stack: [Index, Value][] = [],
        results: number[] = [];
    let current: ListNode | null = head,
        index: number = 0;

    while (current) {
        while (stack.length && stack[stack.length - 1][1] < current.val) {
            const i: number = stack[stack.length - 1][0];
            results[i] = current.val;
            stack.pop();
        }
        stack.push([index, current.val]);

        ++index;
        current = current.next;
    }

    while (stack.length) {
        const [i, value]: [number, number] = stack[stack.length - 1];
        results[i] = 0;

        stack.pop();
    }

    return results;
};

• 栈(优化版)

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
type Index = number;
type Value = number;
function nextLargerNodes(head: ListNode | null): number[] {

    const stack: [Index, Value][] = [],
        results: number[] = [];
    let current: ListNode | null = head,
        index: number = 0;

    while (current) {
        results.push(0);

        while (stack.length && stack[stack.length - 1][1] < current.val) {
            const i: number = stack[stack.length - 1][0];
            results[i] = current.val;
            stack.pop();
        }
        stack.push([index, current.val]);

        ++index;
        current = current.next;
    }

    return results;
};