从输入数字中删除k位后如何获得最少的数字 [英] How to get the least number after deleting k digits from the input number

问题描述

例如输入的数字是24635，删除任意3位后最小的数字是23.

For example, if the input number is 24635, the least number is 23 after deleting any 3 digits.

这与取最小的两位数不同，因为必须保持数字的顺序.

It's not the same as taking the two smallest digits, because the order of the digits must be maintained.

推荐答案

删除 k 个数字意味着保留 n - k 个数字，其中 n是总位数.

Deleting k digits means keeping n - k digits, where n is the total number of digits.

使用按升序排列的堆栈.只要您仍然可以将其设为 n - k 位数并且您的当前元素小于堆栈顶部，您就可以从中删除元素:

Use a stack that you keep sorted ascendingly. You remove elements from it as long as you can still make it to n - k digits and your current element is smaller than the top of the stack:

push(2) => 2
push(4) because 2 < 4 => 24
push(6) because 4 < 6 => 246
pop() because 3 < 6 and we can still end up with 2 digits => 24
pop() for the same reason => 2
push(3) => 23
push(5) => 235

然后只取前 k 个数字 => 23.或者你可以确保永远不会超过 k 个数字，然后最后的堆栈就是你的解决方案.

Then just take the first k digits => 23. Or you can make sure never to push more than k digits, and then the final stack is your solution.

请注意，如果这意味着您将无法构建 k 位数字的解决方案，则您无法弹出元素.为此，您需要检查堆栈中的当前元素数量以及输入数字上当前位置右侧的位数.

Note that you cannot pop elements if that means you will not be able to build a solution of k digits. For this, you need to check the current number of elements in the stack and the number of digits to the right of your current position on the input number.

伪代码:

stack = []
for each d in digits:
  while !stack.empty() and d < stack.top() and (*):
    stack.pop()

  if stack.size() < n - k:
    stack.push(d)

 (*) - exercise, fill in the condition that prevents you 
       from popping elements if you still want to be able to get to a solution.
 Hint: count how many elements the for loop went over already
       and see how many are left. Also consider how many you have left in the stack.

由于每个元素最多进入和离开堆栈一次，复杂度为O(n).

Since each element enters and leaves the stack at most once, the complexity is O(n).

这篇关于从输入数字中删除k位后如何获得最少的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！