移掉k位数字

Tips

题目类型: 单调栈

题目

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

注意:

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

示例

输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219.

输入: num = "10200", k = 1
输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零.

输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字, 剩余为空就是0.

题解

单调栈的作用是要给当前的元素, 找右边/左边第一个比它大/小的位置, 那怎么跟这个题联系到一起呢? 以 num = 1432219 为例:

第一个元素是 1
第二个元素是 4, 因为 4 > 1, 所以不能让 4 去代替 1, 否则数字 4xx 肯定大于 1xx
第三个元素是 3, 因为 3 < 4, 此时可以让 3 去代替 4, 此时最小数字为 13xxx, 它肯定是小于 14xxx 的
...

这样来看, 我们实际上是在找某个元素右边第一个比他小的元素, 以代替该元素, 那自然就是单调栈了.

JavaScript
Rust

/**
 * @param {string} num
 * @param {number} k
 * @return {string}
 */
var removeKdigits = function (num, k) {
  const remainCount = num.length - k
  const stack = []

  for (const digit of num) {
    while (k > 0 && stack.length !== 0 && +stack[stack.length - 1] > +digit) {
      stack.pop()
      k--
    }

    stack.push(digit)
  }

  // 注意:
  // stack 只取前 remainCount 个元素
  // 还要考虑去掉前导零的情况, 这里用正则
  return stack.slice(0, remainCount).join('').replace(/^0+/, '') || '0'
}

pub fn remove_kdigits(num: String, k: i32) -> String {
    let mut stack = vec![];
    let remain_count = num.len() - k as usize;
    let mut k = k;

    for char in num.as_bytes() {
        while k > 0 && !stack.is_empty() && stack[stack.len() - 1] > *char {
            stack.pop();
            k -= 1;
        }

        stack.push(*char);
    }

    let res = stack[0..remain_count]
        .iter()
        .skip_while(|&&c| c == b'0')
        .map(|&c| c as char)
        .collect::<String>();

    if res.len() == 0 {
        return "0".into();
    }

    res
}

题目​

题解​

题目

题解