1. Overview

1.概述

In this tutorial, we’ll see different algorithms allowing us to find the largest number possible after removing the k digits of a number.

在本教程中，我们将看到不同的算法，通过这些算法，我们可以找到去掉一个数字的 k 位后最大的数字。

First, we’ll explain the problem. Then, we’ll see two different algorithms that suit our needs. Finally, we’ll discuss their complexities.

首先，我们将解释这个问题。然后，我们将看到符合我们需求的两种不同算法。最后，我们将讨论它们的复杂性。

2. Problem Explanation

2. 问题解释

First, let’s explain what the goal of the algorithm is. We want to find the largest number possible after removing the k digits of a number.

首先，让我们解释一下算法的目标是什么。我们想找到一个数字去掉 k 位后最大的数字。

For example, consider the number 286281. The number of elements we must remove is 2, so the largest possible number will be 8681. Let’s say we consider another value of k, i.e. 2, so the expected output would be 88.

例如，考虑数字 286281。我们必须删除的元素数是 2，因此最大可能的数字将是 8681。假设我们考虑 k 的另一个值，即 2，那么预期输出将是 88。

3. Using Arithmetic

3.使用算术

In this section, we’ll see the logic explanation and time and space complexity.

在本节中，我们将看到逻辑解释和时空复杂性。

3.1. Logic

3.1.逻辑

Let’s see the logic that would help achieve our goal using some arithmetic. We’ll use the method findLargestNumberUsingArithmetic(num, k) to implement our logic that returns the resultant number.

让我们看看使用一些算术来帮助实现我们目标的逻辑。我们将使用 findLargestNumberUsingArithmetic(num, k) 方法来实现返回结果数的逻辑。

The function findLargestNumberUsingArithmetic(n,k) takes two parameters: $n$ (the original number) and $k$ (the number of digits to remove):

函数 findLargestNumberUsingArithmetic(n,k)接受两个参数： $n$ （原数）和 $k$ （要删除的位数）：

public static int findLargestNumberUsingArithmetic(int num, int k) {
    //...
    return num;
}

We have an outer loop that iterates k times, representing the number of digits to remove:

我们有一个迭代 k 次的外循环，代表要删除的数字个数：

for (int j = 0; j < k; j++) {
    //...
}

For each iteration, it enters an inner loop to remove each digit once. The inner loop calculates the number formed after removing each digit once and compares it with the current maximum number:

每次迭代都会进入一个内循环，将每个数字删除一次。内循环计算每个数字去除一次后形成的数字，并与当前最大数字进行比较：

while (num / i > 0) {
    int temp = (num / (i * 10)) * i + (num % i);
    i *= 10;

    result = Math.max(result, temp);
}
num = result;

After removing the digit, it updates the maximum number if a larger number is found.

移除数字后，如果发现更大的数字，就会更新最大数字。

After k iterations, it returns the remaining number, representing the largest number possible after removing k digits:

在 k 次迭代后，它会返回剩余的数字，代表去除 k 位数后可能的最大数字：

return num;

3.2. Time and Space Complexity

3.2.时空复杂性

The code iterates through k iterations in the outer loop. Inside the outer loop, there’s a while loop that iterates through the digits of num. This loop executes for each digit of the num, which is approximately $log base_{10}$ times since we’re dividing num by 10 in each iteration. Therefore, the time complexity of the inner loop is O(K*log₁₀N).

代码在外循环中迭代 k 次。在外层循环中，有一个 while 循环，用于遍历 num 的各个数字。这个循环执行 num 的每一位数字、约为 $log base_{10} 次数，因为我们在每次迭代中都要将 num 除以 10。因此，内循环的时间复杂度为 O(K*log 10 N)。$

We did not use any extra space, therefore the space complexity will be O(1).

我们没有使用任何额外空间，因此空间复杂度为O(1)。

4. Using Stack

4.使用堆栈

In this section, we’ll see a more optimized approach to improve the complexity.

在本节中，我们将看到一种更优化的方法来提高复杂性。

3.1. Logic

3.1.逻辑

The approach involves using a stack to track the digits of the number while ensuring that the resulting number is maximized.

这种方法包括使用堆栈来跟踪数字的位数，同时确保得到的数字最大。

We’ll use the method findLargestNumberUsingStack(num, k) to implement our logic that returns the resultant number.

我们将使用方法 findLargestNumberUsingStack(num, k) 来实现返回结果数的逻辑。

The function findLargestNumberUsingStack(num,k) takes two parameters: $num$ (the original number) and $k$ (the number of digits to remove).

函数 findLargestNumberUsingStack(num,k)接受两个参数： $num$ （原始数字）和 $num$ （原始数字）。inline”> $k （要删除的位数）。$

Start with converting the number num into a character array or a string to iterate through its digits:

首先将数字 num 转换为字符数组或字符串，以遍历数字：

String numStr = Integer.toString(num); 
int length = numStr.length();

If the number of digits to remove is the same as the length of the input number, we have to return 0:

如果要删除的位数与输入数字的长度相同，则必须返回 0：

if (k == length) return 0;

Otherwise, initialize an empty stack to store the digits:

否则，初始化一个空堆栈来存储数字：

Stack<Character> stack = new Stack<>();

Now, iterate through each digit of the number num and follow the steps:

现在，按照步骤遍历数字 num 的每个数字：

While the stack is not empty, the current digit is greater than the top element of the stack, and the number of remaining digits to remove ( $K$ ) is greater than 0, pop elements from the stack
Push the current digit onto the stack

for (int i = 0; i < length; i++) {
    char digit = numStr.charAt(i);
    while (k > 0 && !stack.isEmpty() && stack.peek() < digit) {
        stack.pop();
        k--;
    }
    stack.push(digit);
}

If there are remaining digits to remove ( $K$ ), pop elements from the stack to satisfy the condition:

如果还有剩余的数字需要删除（ $K ），则从堆栈中弹出元素以满足条件：$

while (k > 0) {
    stack.pop();
    k--;
}

Finally, construct the largest number from the digits remaining in the stack and return the result:

最后，用堆栈中剩余的数字构造最大的数字，并返回结果：

while (!stack.isEmpty()) {
    result.insert(0, stack.pop());
}
return Integer.parseInt(result.toString());

4.2. Time and Space Complexity

4.2.时空复杂性

The algorithm iterates through each digit of the number once, performing constant-time operations within the loop. Therefore, the time complexity will be O(N).

该算法对数字的每个位数迭代一次，在循环中执行恒定时间运算。因此，时间复杂度为O(N)。

The space required is primarily determined by the stack used to store the digits of the number. Therefore, the space complexity will be O(N).

所需空间主要取决于用于存储数字位数的堆栈。因此，空间复杂度将为O(N).。

5. Conclusion

5.结论

In this article, we’ve examined algorithms for finding the largest number possible after removing the k digits of a number. We’ve seen how to achieve that in two ways: arithmetic and stack. We also discussed the time and space complexities of both algorithms, allowing us to choose one wisely according to our needs.

在这篇文章中，我们研究了在去掉一个数字的 k 位数后找出最大数字的算法。我们看到了如何通过两种方法实现这一目标：算术和堆栈。我们还讨论了这两种算法在时间和空间上的复杂性，使我们能够根据自己的需要明智地选择一种算法。

As usual, the complete code examples shown in this article are available over on GitHub.

与往常一样，本文中显示的完整代码示例可在 GitHub 上获取。