从输入的数字中删除k个数字后如何获得最少的数字

Question

例如,如果输入的数字是24635,则23删除任何3位数后的最小数字.

它与取两个最小的数字不同,因为必须保持数字的顺序.

Answer 1

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

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

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数字,然后最后的堆栈是你的解决方案.

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

伪代码:

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).