04137:最小新整数

monotonous-stack, http://cs101.openjudge.cn/practice/04137/

给定一个十进制正整数n(0 < n < 1000000000)，每个数位上数字均不为0。n的位数为m。现在从m位中删除k位(0<k < m)，求生成的新整数最小为多少？例如: n = 9128456, k = 2, 则生成的新整数最小为12456

输入

第一行t, 表示有t组数据；接下来t行，每一行表示一组测试数据，每组测试数据包含两个数字n, k。

输出

t行，每行一个数字，表示从n中删除k位后得到的最小整数。

样例输入

2
9128456 2
1444 3

样例输出

12456
1

何为单调栈？顾名思义，单调栈即满足单调性的栈结构。例如：维护一个整数的单调递增栈。

python

# 23n2300012276(管骏杰）
def removeKDigits(num, k):
    stack = []
    for digit in num:
        while k and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)
    while k:
        stack.pop()
        k -= 1
    return int(''.join(stack))
t = int(input())
results = []
for _ in range(t):
    n, k = input().split()
    results.append(removeKDigits(n, int(k)))
for result in results:
    print(result)

04137:最小新整数 ​

04137:最小新整数