移掉 K 位数字-白红宇

移掉 K 位数字

阅读量：411 次

发布时间：2019-03-06

本文共 1566 字，大约阅读时间需要 5 分钟。

要解决这个问题，我们需要找到一种方法，移除字符串表示的非负整数 num 中的 k 位数字，使得剩下的数字尽可能小。以下是详细的解决方案：

方法思路

我们可以通过使用栈来高效地解决这个问题。栈的作用是维护当前能得到的最小数字序列。具体步骤如下：

遍历数字字符串：从左到右遍历 num 中的每个字符。

维护栈：对于每个字符，检查栈顶元素，如果栈顶元素大于当前字符，弹出栈顶元素，并减少 k 的值，直到栈为空或 k 用完。

处理剩余 k 值：如果遍历结束后 k 还有剩余，移除栈的末尾元素，直到 k 用完。

构造结果：将栈中的元素转换为字符串，去掉前导零，处理特殊情况（如结果为空或有前导零）。

这种方法确保我们在每一步都尽可能保留较小的数字，从而得到最小的结果。

解决代码

import java.util.Deque;import java.util.LinkedList;public class Solution {    public String removeKdigits(String num, int k) {        Deque
   
     deque = new LinkedList<>();        for (int i = 0; i < num.length(); i++) {            char current = num.charAt(i);            while (!deque.isEmpty() && k > 0 && deque.peekLast() > current) {                deque.pollLast();                k--;            }            deque.offerLast(current);        }        // 如果k还剩余，删除后面的数字        while (k > 0) {            deque.pollLast();            k--;        }        // 构建结果字符串        StringBuilder sb = new StringBuilder();        boolean leadingZero = true;        while (!deque.isEmpty()) {            char c = deque.pollFirst();            if (leadingZero && c == '0') {                continue;            }            leadingZero = false;            sb.append(c);        }        // 处理特殊情况        if (sb.length() == 0) {            return "0";        }        return sb.toString();    }}

代码解释

初始化栈：使用双端队列 deque 来模拟栈，用于高效的插入和移除操作。

遍历字符串：逐个字符处理 num 中的每个字符。

栈操作：对于每个字符，检查栈顶元素，如果栈顶元素大于当前字符，弹出栈顶元素并减少 k，直到栈为空或 k 用完。

处理剩余 k：如果遍历结束后 k 还有剩余，移除栈的末尾元素，直到 k 用完。

构造结果：将栈中的元素转换为字符串，去掉前导零，处理特殊情况，返回最终结果。

这种方法确保了在高效的时间复杂度内解决问题，适用于处理较长的数字字符串。

转载地址：http://jgjkz.baihongyu.com/

你可能感兴趣的文章