Remove K Digits ใน C++ : ลบ K หลักเพื่อให้ได้ตัวเลขน้อยที่สุด

ให้ String num แทนจำนวนเต็มบวก และ Integer k ลบ **k หลัก** ออกจาก num ให้ได้ **ตัวเลขที่น้อยที่สุด** (เป็น String, ไม่มี Leading Zeros)

ตัวอย่าง

num = "1432219", k = 3

ลบ 4, 3, 2 (ตัวที่ 2,3,4) -> เหลือ "1219"

Output: "1219"

อัลกอริทึม: Monotonic Stack (Greedy)

หลักการ: **ลบหลักที่ใหญ่กว่าหลักถัดไป** (Peak) เพื่อให้ตัวเลขเล็กลงมากที่สุด

1. เดินผ่าน Digit แต่ละตัวของ num
2. While k > 0 และ Stack ไม่ว่าง และ Stack.top() > currentDigit:
   • Pop Stack (ลบ Peak)
   • k--
3. Push Current Digit เข้า Stack

หลังจบ Loop ถ้า k > 0 -> Pop ท้ายอีก k ตัว (กรณี Non-decreasing เช่น "12345")

สุดท้าย: Build String จาก Stack (Reverse), ตัด Leading Zords, ถ้าว่าง -> "0"

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

class Solution {
public:
    string removeKdigits(string num, int k) {
        string st; // ใช้ String แทน Stack (push_back, pop_back, back)
        for (char c : num) {
            while (k > 0 && !st.empty() && st.back() > c) {
                st.pop_back();
                k--;
            }
            st.push_back(c);
        }
        // ลบเศษ k ที่เหลือ (จากท้าย)
        while (k-- > 0 && !st.empty()) st.pop_back();

        // Build result, trim leading zeros
        int i = 0;
        while (i < st.size() && st[i] == '0') i++;
        string ans = st.substr(i);
        return ans.empty() ? "0" : ans;
    }
};

Input / Output

Input:  "1432219" 3
Output: "1219"

ความซับซ้อน (Complexity)

• Time: O(N) — แต่ละ Digit Push/Pop สูงสุด 1 ครั้ง
• Space: O(N) — Stack/String

จุดสำคัญ (Key Points)

• Greedy: ลบ Peak ทางซ้ายมากที่สุด (Most Significant Digit)
• ใช้ String แทน Stack เร็วกว่าและสะดวกกว่า stack<char>
• จัดการ Leading Zeros และ Empty Result ให้ถูกต้อง

Classic Monotonic Stack Problem ครับ