如何从输入号码删除ķ位数后得到的数目至少 [英] How to get the least number after deleting k digits from the input number

问题描述

例如，如果输入的号码是 24635 ，数量最少的是 23 删除任何3位数之后。

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 - 氏/ code >数字，其中 N 是数字的总数。

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

使用堆栈，你一直排序ascendingly。你从它只要你仍然可以把它删除元素 N - 氏/ code>数字和当前的元素比堆栈的顶部较小的：

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.

伪code：

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）。

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