Remove K Digits

Leave a comment

June 25, 2017 by oneOokay

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.

要怎么要remove digits才能够使得剩下的num为最小的?

从左到右扫描,删除第一个”峰值”(这里的峰值的意思是:大于它右边的neighbor的值),剩下的num为最小的值.

用Stack, stack里面存剩下的digits, pop出的digit代表被删除的digit.

当有k的时候,就可以直接用k,不用另外一个popCounts,直接k–来计数即可.

最后一段可以是一个模板.

   public String removeKdigits(String num, int k) {
        if (k >= num.length()) return "0";
        Stack<Integer> stack = new Stack<>();
        int len = num.length();
        for (int i = 0; i < len; i ++){
             while (!stack.isEmpty() && 
k > 0 && num.charAt(i) - '0' < stack.peek()){
                 stack.pop();
                 k --;             }
             stack.push(num.charAt(i) - '0');
         } 
        while(k > 0 && !stack.isEmpty()){
            stack.pop();
            k --;
        }
        
        if (stack.isEmpty()) return "0";
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()){
            sb.append(stack.pop());
        }
        sb = sb.reverse();
        while(sb.length() > 1 && sb.charAt(0) == '0'){
            sb.deleteCharAt(0);
        }
        return sb.toString();
    }

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: