esc to dismiss

402. 移掉K位数字

题目

给定一个以字符串表示的非负整数 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。

解体思路

这道题的基本思路还是 单调栈 ,不过也是做了点变通。

思考如下:

对于 "1432219" 去掉3个数字,剩下4位数取最小,那么4位数的第一个(也就是万位)一定应该从前四位中取最小的。比如如果是 4431219, 那么最小数就应该是 1219.

而取到第一个数后,第二个数就应该取第一个数之后的数到倒数第3位中最小的数;以此类推,直到最后一个数。

最后再考虑前置0的情况,去除多余的前置0即为答案。

我提交的最终答案:

func removeKdigits(num string, k int) string {
    var mono []int
    size := len(num)

    if k >= size {
        return "0"
    }

  // 1. 先通过单调栈取到第一位
    for i := 0; i < k+1; i++ {
        for len(mono) > 0 && num[i] < num[mono[len(mono)-1]] {
            mono = mono[:len(mono)-1]
        }
        mono = append(mono, i)
    }

  // 2. 从第二位开始取其他的位数
    var result []uint8
    for i := k+1; i < size; i++ {
        result = append(result, num[mono[0]])
        mono = mono[1:]

        for len(mono) > 0 && num[i] < num[mono[len(mono)-1]] {
            mono = mono[:len(mono)-1]
        }
        mono = append(mono, i)
    }

  // 3. 上个循环中,单调栈中最后还有append的元素没有被用到
    start := len(result)
    for i := start; i < size-k; i++ {
        result = append(result, num[mono[i-start]])
    }

  // 4. 消除前置0
    leadingZero := 0
    for _, d := range result {
        if d == '0' {
            leadingZero++
        } else {
            break
        }
    }

    if leadingZero == len(result) {
        leadingZero--
    }

    return string(result[leadingZero:])
}

代码有些冗长。其实就是上述思考中的几点:

  1. 先通过单调栈取到第一位
  2. 从第二位开始取其他的位数
  3. 上个循环中,单调栈中最后还有append的元素没有被用到
  4. 消除前置0

不过消除前置0一段可以用更简洁的 go 语法:

ans := strings.TrimLeft(string(result), "0")
if ans == "" {
    ans = "0"
}

不过官方题解中代码确实更简洁:

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
}

经验教训

提交时错了几次,前置0搞错了(把单独的0也给消除了);另外就是 k+1 条件那里没写对。

golang 的语法还要再熟悉些。

x