Tìm nút lớn hơn tiếp theo cho mỗi nút trong JavaScript

Mô tả vấn đề

Chúng ta cần viết hàm JavaScript nhận vào đầu danh sách liên kết làm đối số duy nhất. Danh sách chứa dữ liệu số. Mỗi nút có thể có giá trị lớn hơn tiếp theo: với node_i, next_larger(node_i) là node_j.val sao cho j > i, node_j.val > node_i.val, và j nhỏ nhất có thể. Nếu không tồn tại j, giá trị là 0.

Hàm chuẩn bị và trả về mảng mà phần tử tương ứng là phần tử lớn hơn tiếp theo cho phần tử trong danh sách.

Ví dụ, nếu danh sách là:

Thì đầu ra nên là:

const output = [7, 0, 5, 5, 0];

Giải thích đầu ra

Vì phần tử lớn hơn tiếp theo của 2 là 7, của 7 không có phần tử lớn hơn, v.v.

Ví dụ minh họa

Mã thực hiện (stack đơn điệu):

class Node{ 
  constructor(data){ 
    this.data = data; 
    this.next = null; 
  }; 
}; 
class LinkedList{ 
  constructor(){ 
    this.head = null; 
    this.size = 0; 
  }; 
}; 
LinkedList.prototype.add = function(data){ 
  const newNode = new Node(data); 
  let curr; 
  if(this.head === null){ 
    this.head = newNode; 
  }else{ 
    curr = this.head; 
    while (curr.next) { 
      curr = curr.next; 
    } 
    curr.next = newNode; 
  }; 
  this.size++; 
}; 
const list = new LinkedList(); 
list.add(2); 
list.add(7); 
list.add(4); 
list.add(3); 
list.add(5); 
const nextGreater = (head) => { 
  const arr = []; 
  const res = []; 
  let curr = head; 
  let currentIndex = 0; 
  while(curr){ 
    while (arr.length > 0 && curr.data > arr[arr.length - 1][1]) { 
      const [index] = arr.pop(); 
      res[index] = curr.data; 
    }; 
    arr.push([currentIndex, curr.data]); 
    currentIndex += 1; 
    curr = curr.next; 
  }; 
  for(let i = 0; i < currentIndex; i++){ 
    if(res[i] === undefined){ 
      res[i] = 0; 
    }; 
  }; 
  return res; 
}; 
console.log(nextGreater(list.head));

Đầu ra

Kết quả trong console sẽ là:

[ 7, 0, 5, 5, 0 ]