最大新整数

[编程题]最大新整数

热度指数：2758 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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

输入描述:

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

输出描述:

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

示例1

输入

1432219 3

输出

算法知识视频讲解

Python

sky游荡

维护一个单调栈，栈顶元素比当前小的，出栈，计数减一。大的入栈。

最后若计数k1没用完，就去掉栈顶的k1个元素，

否则就将数组剩余的元素追加在栈里。

ss ,k= input().split()
k,nums= int(k),[]
for d in ss:
    nums.append(d)
stack,i  = [],0
while k>0 and i<len(nums):    
    if (stack and nums[i]<=stack[-1])&nbs***bsp;not stack:
        stack.append(nums[i])
        i+=1
    elif stack and nums[i]>stack[-1]:
        stack.pop()        
        k-=1
if k==0:
    stack+=nums[i:]
else:
    stack = stack[0:-k]
            
print(''.join(list(map(str,stack))))

编辑于 2020-04-26 16:36:19 回复(0)

Python

白色纯度

我来一个python最优的解法：

1. 用一个栈记录符合条件的数字，只要当前循环下的数字比栈末尾的数字大，我们就从后向前删除栈内的数字，并更新K的的值，记做k。直至k==0 或者数字不大于栈末尾的数字为止。

2 如果循环之后，K还有剩余k，那么删除栈内后k个数字即可。

if __name__ == "__main__":
    s, K = raw_input().strip().split()
    s = list(s)
    k = int(K)
    ans = [s[0]]
    for i in s[1:]:
        while ans and k>0:
            if i>ans[-1]:
                ans.pop()
                k -= 1
            else:
                break
        ans.append(i)
    if k>0:
        ans = ans[:-k]
    print(''.join(ans))

发表于 2019-08-22 19:16:23 回复(1)

Python

ElonB

 """"
找到[0,K]区间内最大值对应的第一个下标 idx，
移除idx之前的所有数字，更新K = K-idx，保留idx对应的数字，对idx之后的数字串重复上一步骤
例如：输入 41681991713273619813 10 输出 9977619813
对s[0:10] 求最大值对应下标 idx=5，
移除s[0:5)，K=10-5=5 ，输出s[idx]即9，对s[6:end)重复操作
对s[6:6+5] 求 idx=0，移除s[6:6+idx)即此次不移除，输出s[6+idx]即9，对s[7:end)重复操作
对s[7:7+5] 求 idx=1，移除s[7:7+idx)，K=5-1=4，输出s[7+idx]即s[8]=7，对s[9:end)重复操作
对s[9:9+4] 求 idx=3，移除s[7:7+idx)，K=4-3=1，输出s[9+idx]即s[12]=7，对s[13:end)重复操作
对s[13:13+1] 求 idx=1，移除s[13:13+idx)，K=1-1=0，输出s[13+idx]即s[14]=6，输出s[15:end)
"""

if __name__ == "__main__":
    s, K = input().strip().split()
    s = list(s)
    K = int(K)
    t = 0
    ans = []
    while K:
        if K == len(s) - t:
            t = len(s)
            break
        idx = s[t:t + K + 1].index(max(s[t:t + K + 1]))
        ans.append(s[t + idx])
        K -= idx
        t += idx + 1
    ans += s[t:]
    print(''.join(ans))

发表于 2019-07-15 20:12:45 回复(0)