LeetCode 402. Remove K Digits

402. Remove K Digits

Description Submission Solutions Add to List

Total Accepted: 13739
Total Submissions: 52825
Difficulty: Medium
Contributors: Admin

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:

The length of num is less than 10002 and will be ≥ k.
The given num does not contain any leading zero.

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.

Subscribe to see which companies asked this question.

【题目分析】

即使知道一个题目的解题思路，如何用代码简洁优美地来表达也是一种艺术。

这个题目的大意是去掉一个数中出现的若干数字，使得得到的数是可能得到的结果中最小的那个。

【思路分析】

通过观察不难发现，我们每次都去掉那个从头开始搜索的局部最大值，采用这种贪心策略可以得到最优解。在得到结果后我们还要对开始字符为0的特殊情况进行处理。但是在实现的时候，自己的代码不仅冗余，而且对边界情况处理很不到位，导致最后的结果不正确。看了讨论区大神的代码，真是很惭愧。

【java代码】

 1 public class Solution {
 2     public String removeKdigits(String num, int k) {
 3         int digits = num.length() - k;
 4         char[] stk = new char[num.length()];
 5         int top = 0;
 6         // k keeps track of how many characters we can remove
 7         // if the previous character in stk is larger than the current one
 8         // then removing it will get a smaller number
 9         // but we can only do so when k is larger than 0
10         for (int i = 0; i < num.length(); ++i) {
11             char c = num.charAt(i);
12             while (top > 0 && stk[top-1] > c && k > 0) {
13                 top -= 1;
14                 k -= 1;
15             }
16             stk[top++] = c;
17         }
18         // find the index of first non-zero digit
19         int idx = 0;
20         while (idx < digits && stk[idx] == '0') idx++;
21         return idx == digits? "0": new String(stk, idx, digits - idx);
22     }
23 }