หาโหนดถัดไปที่มีค่ามากกว่าสำหรับแต่ละโหนดใน JavaScript

ปัญหา

เราต้องเขียนฟังก์ชัน JavaScript ที่รับหัวของลิงก์ลิสต์เป็นอาร์กิวเมนต์เดียว

ลิงก์ลิสต์นี้มีข้อมูลตัวเลข แต่ละโหนดอาจมีค่าที่มากกว่าตัวเองอยู่ข้างหน้า: สำหรับ node_i, next_larger(node_i) คือ node_j.val ที่ทำให้ j > i, node_j.val > node_i.val และ j เป็นค่าที่น้อยที่สุดที่เป็นไปได้ หากไม่มี j ให้ค่าถัดไปที่มากกว่าเป็น 0

ฟังก์ชันควรเตรียมและคืนอาร์เรย์ที่สมาชิกแต่ละตัวคือค่าถัดไปที่มากกว่าของโหนดในลิสต์

ตัวอย่างเช่น ถ้าลิสต์เป็น

ผลลัพธ์ควรเป็น

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

คำอธิบายผลลัพธ์:

เพราะค่าถัดไปที่มากกว่าของ 2 คือ 7 สำหรับ 7 ไม่มีค่ามากกว่า และต่อไป...

ตัวอย่างโค้ด

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));

ผลลัพธ์

ผลลัพธ์ในคอนโซลจะเป็น

[ 7, 0, 5, 5, 0 ]