給定一個非負整數的字串表示
num和整數k，移除k個數字使得剩餘數字組成的數最小。回傳該最小數的字串表示。
Example:
Input: num = “1432219”, k = 3 Output: “1219”
Intuition
TIP
核心思路：用單調遞增堆疊，當新數字比棧頂小時就彈出棧頂（相當於移除較大的數字），最多移除 k 個。
- 要讓數字最小，高位數字越小越好
- 從左到右掃描，如果當前數字比前一個小，就應該移除前一個（貪心策略）
- 這就是維護單調遞增堆疊的過程
Approaches
1. Brute Force: Remove One Drop per Pass — O(n·k) / O(n)
- Idea: 每輪從左找第一個「比右鄰大」的數字移除（無則移除最後一個），重複 k 輪
- Time:
O(n·k)- k 輪、每輪掃描 O(n) - Space:
O(n)- 字串重建
class Solution {
fun removeKdigits(num: String, k: Int): String {
var s = num
repeat(k) {
var i = 0
while (i < s.length - 1 && s[i] <= s[i + 1]) i++ // 第一個下降點（或末尾）
s = s.removeRange(i, i + 1)
}
return s.trimStart('0').ifEmpty { "0" }
}
}⭐ 2. Monotonic Increasing Stack + Greedy — O(n) / O(n)
- Idea: 遍歷每個數字，用 while 迴圈彈出所有大於當前數字的棧頂（同時遞減 k），最後去除前導零
- Time:
O(n)- 每個數字最多入棧出棧各一次 - Space:
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: 「移除元素使結果最小/最大」的問題 = 單調堆疊 + 貪心
- Key trick: 三個容易遺漏的邊界情況：(1) k 還有剩餘時從尾端移除；(2) 去除前導零；(3) 結果為空時回傳 “0”