牛客网XM26最大新整数

题目描述

有一十进制正整数，移除其中的 K 个数，使剩下的数字是所有可能中最大的。
假设：
字符串的长度一定大于等于 K
字符串不会以 0 开头

输入描述:

一行由正整数组成的数字字符串，和一个正整数 K，两个数据用空格隔开，如：1432219 3。
字符串长度不超过2000，K<=2000。

输出描述:

移除 K 位后可能的最大的数字字符串。
如 1432219 移除 1, 2, 1 这 3 个数字后得到 4329，为所有可能中的最大值。

示例1

输入

1432219 3

输出

解题思路

拿到这个题首先想到的问题是：如何能保证数字的高位更大？

假设K==1

一眼就能看到应当删除最高位的1，得到432219。这个时候问题简化成删除某一位数字使结果数值达到最大，也就是求前N位中第一个最小值，然后删除它。示例1中，最高位的1，即是最小的值。

考虑另一种用例，4444129，删除前四位中任一个，结果都是444129；当看到第5位时，结果变成了444429。看到这里时，“感觉“问题变成了在前N位中求第一个最小值。

假设K==2

当K为2时，情况变得复杂一些了。

对于示例1，我们先按K==1的情况删除一位1。我们在余下的数字（432219）中再按k=1来求最小值，得到需要删除的数字，发现余下的数字中仍然是1最小，删除1得到43229。

假设K==3

K为3时，仍然在上一步的基础上，删除最小值，得到4329。与答案吻合。

def func(s, K):
    k = int(K)
    while k > 0:
        index = 0
        to_delete = s[0]
        for idx, num in enumerate(s):
            if num < to_delete:
                index = idx
                to_delete = num
        s = (s[:index] + s[index + 1:])
        k -= 1
    return s
if __name__ == '__main__':
    print(func('1432219','3'))

再回过头来看解题思路，偏离了使最高位最大的主旨，代码变成了求最小值。上面的代码还有另外一个问题，代码复杂度为O(n2)，可能会超时。

怎么样能够使高位相对最大呢？有一种算法能够很好的支撑这种目标—单调栈。

单调栈的定义

在一个栈里面存放的数据都是有序的。

如果是升序排列，为单调递增栈

如果是降序排列，为单调递减栈

单调栈的性质

能快速地得知当前位置左(右)侧比他大（或小）的数据的位置，时间复杂度是O(1)。

举例

求解数组中元素右边第一个比它小的元素的下标，从前往后，构造单调递增栈；
求解数组中元素右边第一个比它大的元素的下标，从前往后，构造单调递减栈；
求解数组中元素左边第一个比它小的元素的下标，从后往前，构造单调递减栈；
求解数组中元素左边第一个比它小的元素的下标，从后往前，构造单调递增栈。

def func(s, K):
    k = int(K)
    stack = []

    for idx, num in enumerate(s):
        # 避免无效循环，K为0时退出
        if k == 0:
            break
        while stack and num > stack[-1] and k > 0:
            stack.pop()
            k -= 1
        stack.append(num)
    
    result = (''.join(stack) + (s[idx + 1:] if idx == len(s) - 1 else s[idx:]))
    # 这里加了特判，有可能 k会大于0
    if k > 0:
        return result[:len(s) - int(K)]
    return result


if __name__ == '__main__':
    s, K = input().strip().split()
    print(func(s, K))

由于格式问题，建议查看公众号文章，传递门