LeetCode: 402-Remove K Digits 解題紀錄

Last Updated on 2022-02-18 by Clay

題目

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

Constraints:

• 1 <= k <= num.length <= 105
• num consists of only digits.
• num does not have any leading zeros except for the zero itself.

題目給定一組全部由數字組成的字串以及一個 k 值，k 值代表著我們可以移除的數字數量。而我們要找到的，就是移除完 k 個數字後，剩下的字串所代表的值如何才是最小。

---

解題思路

一開始我只是模模糊糊有個概念，數字排越前面的越重要、但是同時也要那些數字是較小的...... 但是卻沒想出一個比較好的解法。

接著嘗試使用暴力解，窮舉所有可能性。想當然爾，馬上就吃到了 TLE。

看了一下他人的解答，這才想通我們希望組成的數字應該是由小排到大，所以可以建立一個 stack 的結構，遍歷比較字串中的數值和 stack 的頂部。

如果 stack 頂部的值大於當前搜尋到的值，那麼就彈出 stack 頂部（同時別忘了減去一次 k 的次數）—— 這個步驟要一直做到 k 沒有次數、stack 為空、或是 stack 頂部的值終於小於當前值為止。

接著將當前值傳入 stack 中，成為新的頂部值。

當所有字串中的數值遍歷完後，可能存在著 k 仍然有次數的情況，這多半是由於 stack 中有同樣的數字，所以按照 k 值彈出 stack 頂部值即可。

在將 stack 中的值重新組成字串時，別忘了第一個值為 0 的情況要去除掉。當然你也可以一開始就在 stack 僅有一值且為 0 的時候就將其去掉。

複雜度

基本就是遍歷一次、stack 彈出所有儲存值一次、反轉答案的字串（因為 stack 彈出來的順序是反過來的），故時間複雜度為 O(n)。

空間複雜度由於建立了 stack，故應為 O(n)。

Time Complexity	O(n)
Space Complexity	O(n)

C++ 範例程式碼

class Solution {
public:
    string removeKdigits(string num, int k) {
        // Base case
        if (num.size() == k) return "0";
        
        // Init
        string ans;
        stack<char> s({num[0]});
        
        // Current element need to larger than the next one
        for (int i=1; i<num.size(); ++i) {
            while (k > 0 && !s.empty() && s.top() > num[i]) {
                --k;
                s.pop();
            }
            
            s.push(num[i]);
            
            // Remove the zero at the begin
            if (s.size() == 1 && s.top() == '0') {
                s.pop();
            }
        }
        
        // We still need to remove some elements
        while (k > 0 && !s.empty()) {
            --k;
            s.pop();
        }
        
        // Combine the answer
        while (!s.empty()) {
            ans.push_back(s.top());
            s.pop();
        }
        
        // Reverse
        reverse(ans.begin(), ans.end());
        
        if (ans.size() == 0) return "0";
        else return ans;
    }
};

Python 範例程式碼

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        # Base case
        if len(num) == k: return "0"
        
        # Init
        s = [num[0]]
        
        # Current element need to larger than the next one
        for i in range(1, len(num)):
            while k > 0 and s and s[-1] > num[i]:
                k -= 1
                s.pop()
            
            s.append(num[i])
            
            # Remove the zero at the begin
            if len(s) == 1 and s[0] == "0":
                s.pop()
        
        # We still need to remove some elements
        while k > 0 and s:
            k -= 1
            s.pop()

        
        # Combine the answer
        ans = "".join(s)
        
        if len(ans) == 0: return "0"
        else: return ans

---

References

• https://leetcode.com/problems/remove-k-digits/

---

Read More

• LeetCode 解題紀錄目錄