หาตัวเลขน้อยที่สุดหลังลบ n หลัก (Remove K Digits) ใน JavaScript

ปัญหา

รับตัวเลข m (สตริง) และ n ลบ n หลัก เพื่อให้ตัวเลขที่เหลือน้อยที่สุด

ตัวอย่าง

const m = '45456757'; const n = 3;

ลบ 5,6,7 → '44557'

โค้ดตัวอย่าง (Greedy + Stack)

const m = '45456757'; const n = 3; 
const removeDigits = (m, n, stack = []) => { 
  let arr = m.split('').map(Number); 
  for(let el of arr){ 
    while (n && stack.length && el < stack[stack.length - 1]){ stack.pop(); --n; } 
    stack.push(el); 
  } 
  let begin = stack.findIndex(el => el > 0); 
  let end = stack.length - n; 
  return (!stack.length || begin == -1 || begin == end) ? "0" : stack.slice(begin, end).join('').toString(); 
}; 
console.log(removeDigits(m, n));

คำอธิบาย

Greedy Algorithm: ใช้ Stack เก็บหลักที่ดีที่สุด หลักซ้ายมีค่าน้ำหนักมากกว่า จึงพยายามให้หลักซ้ายสุดน้อยที่สุด

ผลลัพธ์

44557