leetcode-402-Remove-K-Digits

发表于   |  

TOREVIEW

描述

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

Example 1:

1
2
3
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:

1
2
3
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:

1
2
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.

Constraints:

  • 1 <= k <= num.length <= 105
  • num consists of only digits.
  • num does not have any leading zeros except for the zero itself.

分析

题目大意是，给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。单调栈问题。时间复杂度是 O(n), 空间复杂度是 O(n)

解决方案1(Python)

1
2
3
4
5
6
7
8
9
10
class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []
        remain = len(num) - k
        for digit in num:
            while k and stack and stack[-1] > digit:
                stack.pop()
                k -= 1
            stack.append(digit)
        return ''.join(stack[:remain]).lstrip('0') or '0'

解决方案2（Golang）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func removeKdigits(num string, k int) string {
    if len(num) == k {
        return "0"
    }
    result := make([]byte, 0)
    
    for i := 0; i < len(num); i++ {
        if len(result) == 0 {
            result = append(result, num[i])
            continue
        }
        for ; k > 0 && len(result) > 0 && result[len(result)-1] > num[i]; {
            result = result[:len(result)-1]
            k--
        }
        result = append(result, num[i])
    }
    
    result = result[:len(result) - k]
    for result[0] == '0' && len(result) > 1 {
        result = result[1:]
    }
    return string(result)
}

相关问题

题目来源