1019. Next Greater Node In Linked List

解法I - BF

实现

遍历链表，存进数组，然后二重循环

提示I - One Pass

实现

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {number[]}
 */
const nextLargerNodes = function(head) {
  const stack = [];
  const result = [];

  let p = head;
  let counter = 0;
  while (p !== null) {
    const current = p.val;

    while (stack.length > 0 && stack[stack.length - 1].val < current) {
      const {index} = stack.pop();
      result[index] = current;
    }

    stack.push({
      index: counter,
      val: current
    });

    result.push(0);

    p = p.next;
    counter += 1;
  }

  return result;
};

提示II - Recursive

实现

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {number[]}
 */
var nextLargerNodes = function (head) {
    const values = [];
    const result = [];
    const hasCalculated = [];

    let p = head;
    let i = 0;
    while (p !== null) {
        values.push(p.val);
        result.push(0);
        hasCalculated.push(false);
        p = p.next;
    }

    const f = (p, v) => {
        if (p === values.length) {
            return;
        }
        if (hasCalculated[v]) {
            return;
        }

        if (values[p] > values[v]) {
            result[v] = values[p];
            hasCalculated[v] = true;
        } else {
            f(p + 1, v);
        }

        f(p + 1, p);
    }

    f(0, 0);

    return result;
}

提示III - DP

实现

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {number[]}
 */
var nextLargerNodes = function (head) {
    const values = [];
    const result = [];

    while (head !== null) {
        values.push(head.val);
        result.push(0);
        head = head.next;
    }

    for (let i = result.length - 2; i >= 0; i --) {
        if (values[i + 1] > values[i]) {
            result[i] = values[i + 1];
        } else {
            for (let j = i + 1; j < result.length - 1; j ++) {
                if (result[j] > values[i] || result[j] === 0) {
                    result[i] = result[j]; 
                    break;
                }
            }
        }
    }

    return result;
};