移掉K位数字-leetcode-402

涉及知识点：贪心,栈

题目

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

注意:

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

输入/输出示例：

Example 1:

Input:

num = "1432219", k = 3

Output:

"1219"

Explanation: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。

Example 2:

Input:

num = "10200", k = 1

Output:

"200"

Explanation: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

Example 3:

Input:

num = "10", k = 2

Output:

"0"

Explanation: 从原数字移除所有的数字，剩余为空就是0。

思路描述

思路 0

详细描述：思路，从左到右，找第一个比后面大的字符，删除，清零，k次扫描。

时间复杂度：o(n*k)
空间复杂度：o(1)

代码：

class Solution {  
    public String removeKdigits(String num, int k) {        if (num.length() == k) return "0";        StringBuilder s = new StringBuilder(num);        for (int i = 0; i < k; i++) {            int idx = 0;            for (int j = 1; j < s.length() && s.charAt(j) >= s.charAt(j - 1); j++) idx = j;            s.delete(idx, idx + 1);            while (s.length() > 1 && s.charAt(0) == '0') s.delete(0, 1);        }        return s.toString();    }}

思路 1

详细描述：在一定的范围内逐步选取最小的数字。

在第一次循环中，num = 1432219, k=3，此时我们要删去k=3个数字，保留n-k=7-3=4个数字。
最终要挑选4个字符，那么我们先来挑选千位的字符，，由于挑选完千位后还需要挑选百位，十位，个位这三个位置的字符，所以千位能选择的范围只能在1432之间,因为要留出末尾的219这三个字符供百位、十位、个位去挑选。
1432中最小的值是1，所以千位的值选好了，就是1，接下来就是从千位后面的432219中去挑选百位值，可以发现挑选每一位的值是一个递归的过程。
start = 0, end = k。也就是要在[start,end]中选取一个最小的进行保留，返回最小数字的下标minIndex。而在下次循环中，start = minIndex+1, end++ ，也就是在[start,end]中选择下一个最小的数字。以此类推，直至所有数字都选取完毕。

注意：当返回的下标minIndex及后面的字符串的长度 = 还需要保留的字符串的长度的时候，直接返回

时间复杂度：o(n*k)
空间复杂度：o(1)

代码：

func removeKdigits(num string, k int) string {  
    if 0 == k {        return num    }    if k == len(num) {        return "0"    }    result := ""    i := len(num)-k    for {        if i == 0 {            break        }        minIndex := 0        for  j := 0; j < len(num)-(i-1); j++ {            if num[j] < num[minIndex] {                minIndex = j            }        }        // 优化        if len(num)- minIndex == i {            result = result + num[minIndex:]            break        }        result += num[minIndex:minIndex+1]        num = num[minIndex+1:]        i--    }    // 前导0    ans := strings.TrimLeft(result, "0")    if ans == "" {        ans = "0"    }    return ans}

思路2: 贪心 + 单调栈（一般可用栈、队列、双端队列、双指针实现）

详细描述：

遍历字符串，逐个入栈,若新来的比栈顶小，则栈顶出栈 ,出栈相当于移除动作，需次数并与 k 比较，别删多了
移除头部零有 ‘0’,全空，return “0”,构建字符串，顺序返回整个单调栈元素.
时间复杂度：o(n+k)
空间复杂度：o(n)

代码：

func removeKdigits(num string, k int) string {  
    stack := []byte{}    
    for i := range num {
        digit := num[i]
        for k > 0 && len(stack) > 0 && digit < stack[len(stack)-1] {
            stack = stack[:len(stack)-1]
            k--        
        }
        stack = append(stack, digit) 
    }
    stack = stack[:len(stack)-k]
    ans := strings.TrimLeft(string(stack), "0")
    if ans == "" {
        ans = "0"    
    }
    return ans
}