2022-02-19

Leetcode 402 - Remove K Digits

Problem#

給你一個只有非負整數的字串 num 和整數 k，要你回傳刪掉 k 個數字後，之中最小的整數

1
2
3

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.

想法#

假如結果要最小的，那一定要從左邊開始刪數字，因為這樣刪掉的數字所佔的位數比較大；且只能刪 k 個數字，所以會想要挑最大的刪。
掃描 nums ，如果當前的數字比前一位數字小(即 $a_i > a_{i-1}$ )，則刪掉前一位數字( $a_{i-1}$ )，如果前前位( $a_{-2}$ )也比當前小，則繼續刪，以此類推，直到刪到 k 次為止。
最後如果沒有刪完 (k還有剩)，因為剩下的數字是單調遞增( $a_i < a_{i+1}$ )的，所以就從右邊開始刪(因為數字最大)。最後，把前面數字的0去除即是答案。

時間複雜度: O(N)
- 從左往右掃一次
空間複雜度: O(N)
- 存放答案陣列

AC Code#

        Copy
        class Solution {
    string removeKdigits(string num, int k)
        string ans;
        for(char c : num)
            // if current digit is greater than the previous digit, deletes it
            while(!ans.empty() && ans.back() > c && k)
                ans.pop_back();
            ans.push_back(c);
        // if remaining nums are monotone ascending, delete digits from back
        while(k--)
            ans.pop_back();
        // Remove the leading zeros 
        int start = 0;
        while(ans[0] == '0' && ans[start] == '0')
            start++;
        ans = ans.substr(start, ans.size()-start);
        return ans == "" ? "0" : ans;

      

view raw leetcode/402.cpp delivered with ❤ by emgithub

賞析#

https://leetcode.com/problems/remove-k-digits/discuss/629860/Java-or-C%2B%2B-or-Python3-or-easy-explanation

	class Solution {
	public:
	string removeKdigits(string num, int k)
	{
	string ans;

	for(char c : num)
	{
	// if current digit is greater than the previous digit, deletes it
	while(!ans.empty() && ans.back() > c && k)
	{
	ans.pop_back();
	k--;
	}

	ans.push_back(c);
	}
	// if remaining nums are monotone ascending, delete digits from back
	while(k--)
	ans.pop_back();

	// Remove the leading zeros
	int start = 0;
	while(ans[0] == '0' && ans[start] == '0')
	start++;
	ans = ans.substr(start, ans.size()-start);

	return ans == "" ? "0" : ans;
	}
	};