leetcode.402. 移掉K位数字(remove-k-digits)

左手的ㄟ右手 2022-12-21 06:19 84阅读 0赞

# 402. 移掉K位数字(remove-k-digits) #

给定一个以字符串表示的非负整数 *num*，移除这个数中的 *k* 位数字，使得剩下的数字最小。

注意:

*  *num* 的长度小于 10002 且 *≥ k*。
 *  *num* 不会包含任何前导零。
 *

示例 1 :

输入: num = "1432219", k = 3
    输出: "1219"
    解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。

示例 2 :

输入: num = "10200", k = 1
    输出: "200"
    解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

示例 3 :

输入: num = "10", k = 2
    输出: "0"
    解释: 从原数字移除所有的数字，剩余为空就是0。

# 代码与思路 #

package remove_k_digits;
    
    import java.util.Deque;
    import java.util.LinkedList;
    
    public class Solution2 { 
    	
        public String removeKdigits(String num, int k) { 
        	//使用双端队列来代替栈
            Deque<Character> deque = new LinkedList<Character>();
            //栈顶元素大于当前元素就移除
            int length = num.length();
            for (int i = 0; i < length; ++i) { 
                char digit = num.charAt(i);
                while (!deque.isEmpty() && k > 0 && deque.peekLast() > digit) { 
                    deque.pollLast();
                    k--;
                }
                deque.offerLast(digit);
            }
            
            //如果我们删除了 m 个数字且m<k，这种情况下我们需要从序列尾部删除额外的 k−m 个数字
            for (int i = 0; i < k; ++i) { 
                deque.pollLast();
            }
            
            //如果最终的数字序列存在前导零，我们要删去前导零
            StringBuilder ret = new StringBuilder();
            boolean leadingZero = true;
            while (!deque.isEmpty()) { 
                char digit = deque.pollFirst();
                if (leadingZero && digit == '0') { 
                    continue;
                }
                leadingZero = false;
                ret.append(digit);
            }
            return ret.length() == 0 ? "0" : ret.toString();
        }
        
        public static void main(String[] args) { 
    // String num = "1432219";
    // String num = "1456789";
    		String num = "9000009";
    		int k = 3;
    		System.out.println("num="+num+" k="+k);
    		System.out.println(new Solution2().removeKdigits(num, k));
    	}
        
    }
    //资料/remove-k-digits/solution/yi-diao-kwei-shu-zi-by-leetcode-solution/

cpp代码

class Solution { 
    public:
        string removeKdigits(string num, int k) { 
            vector<char> stk;
            for (auto& digit: num) { 
                while (stk.size() > 0 && stk.back() > digit && k) { 
                    stk.pop_back();
                    k -= 1;
                }
                stk.push_back(digit);
            }
    
            for (; k > 0; --k) { 
                stk.pop_back();
            }
    
            string ans = "";
            bool isLeadingZero = true;
            for (auto& digit: stk) { 
                if (isLeadingZero && digit == '0') { 
                    continue;
                }
                isLeadingZero = false;
                ans += digit;
            }
            return ans == "" ? "0" : ans;
        }
    };