移掉 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();    }}