leetcode

LeetCode 402：Remove K Digits

Problem

LeetCode 402：Remove K Digits

1. 题目简述

给出一个数字组成的字符串num，从中去除k位后使其得到的数字最小。注意，要将首位的0全部去掉，举例：

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.

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.

2. 算法思路

贪心法 + Stack：

先看去除一位的情况，去除一位时，一位一位从前向后数，找到第一个逆序数对时，即第k + 1位小于第k位，此时，删除第k位。去除多位的情况重复以上操作，直至满足要求。

Corner Case：

  1. 首先注意如果剩余数字的位数为空，则应该返回“0”，而不是空字符串。
  2. 在最后去除首位0的时候，注意数组不能越界，存在去除数字后为“0000…0”的情况。

3. 解法

这里参考了讨论区的大佬的做法，用数组替代了stack，使用了一个top变量俩控制栈顶，十分巧妙。

class Solution {
    public String removeKdigits(String num, int k) {
        int length = num.length();
        int digits = length - k;
        char[] stack = new char[length];
        int top = 0;
  
        for(int i = 0; i < length; i++) {
            char temp = num.charAt(i);
            while(k > 0 && top > 0 && stack[top - 1] > temp) {
                top--;
                k--;
            }
            stack[top++] = temp;
        }
        // attention : corner case
        int startZeros = 0;
        while(startZeros < digits && stack[startZeros] == '0') {
            startZeros++;
        }
        // attention : corner case
        return startZeros == digits ? "0" : new String(stack, startZeros, digits - startZeros);
  
    }
}