c - 如何从输入数字中删除k位后得到最少的数字

Question

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

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

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