402. Remove K Digits

Medium

Description

給定一個非負整數的字串表示 num 和整數 k，移除 k 個數字使得剩餘數字組成的數最小。回傳該最小數的字串表示。

Example:

Input: num = “1432219”, k = 3 Output: “1219”

Intuition#

核心思路：用單調遞增堆疊，當新數字比棧頂小時就彈出棧頂（相當於移除較大的數字），最多移除 k 個。

要讓數字最小，高位數字越小越好
從左到右掃描，如果當前數字比前一個小，就應該移除前一個（貪心策略）
這就是維護單調遞增堆疊的過程

Approaches#

⭐1: 單調遞增堆疊 + 貪心#

概念: 遍歷每個數字，用 while 迴圈彈出所有大於當前數字的棧頂（同時遞減 k），最後去除前導零
時間複雜度: O(n) - 每個數字最多入棧出棧各一次
空間複雜度: O(n)

class Solution {
    fun removeKdigits(num: String, k: Int): String {
        var remaining = k
        val stack = ArrayDeque<Char>()

        for (digit in num) {
            while (remaining > 0 && stack.isNotEmpty() && stack.last() > digit) {
                stack.removeLast()
                remaining--
            }
            stack.addLast(digit)
        }

        // 若還沒移除夠 k 個（例如遞增序列），從尾端移除
        repeat(remaining) {
            stack.removeLast()
        }

        // 去除前導零
        val result = stack.joinToString("").trimStart('0')

        return if (result.isEmpty()) "0" else result
    }
}

🔑 Takeaways#

Pattern: 「移除元素使結果最小/最大」的問題 = 單調堆疊 + 貪心
關鍵技巧: 三個容易遺漏的邊界情況：(1) k 還有剩餘時從尾端移除；(2) 去除前導零；(3) 結果為空時回傳 “0”