leetcode

leetcode 402题

Posted by franki on October 6, 2022

leetcode 402题 移掉 K 位数字

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

示例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 。

思路

循环整个字符串，使用一个栈来保存当前的进出栈情况，当前进栈的元素如果比栈顶的元素小的话，那么那个栈顶元素出栈，循环这个过程，直到当前的元素不再小于栈顶元素，然后取前面 length - k 位数字，注意边界情况处理，即可。

代码

/**
 * @param {string} num
 * @param {number} k
 * @return {string}
 */
const removeKdigits = (num, k) => {
    const length = num.length;

    if (k === length) {
        return '0';
    }

    let res = [];

    for (let i = 0; i < length; i++) {
        const c = num[i];

        while (k > 0 && res.length > 0 && c < res[res.length - 1]) {
            res.pop();
            k--;
        }

        res.push(c);
    }

    res = res.slice(0, res.length - k);

    while (res.length > 1 && res[0] === '0') {
        res = res.slice(1);
    }

    return res.join('');
};

复杂度分析:

  • 时间复杂度: O(N^2)
  • 空间复杂度：O(N)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG
    FRIENDS