求通过删除X中若干数字(保持顺序)得到的最接近Y的较大数的解法思路
求通过删除X中若干数字(保持顺序)得到的最接近Y的较大数的解法思路
嗨,这个问题可以用贪心策略结合回溯剪枝来解决,我给你拆解成清晰的步骤,照着来就能搞定:
一、预处理:转字符串方便逐位处理
把整数X和Y转换成字符串sX和sY,记它们的长度分别为n(X的位数)和m(Y的位数)。根据题目条件X > Y,可以确定n >= m——因为如果n < m,X作为n位数必然小于m位数的Y,和前提矛盾,所以不用考虑这种情况。
二、优先寻找长度等于Y的符合条件的子序列
我们的核心目标是找到长度为m的、大于Y的最小子序列——相同位数下,越接近Y的数(也就是最小的大于Y的数)就是我们要的结果。具体做法:
- 逐位确定子序列的每一位:
- 从左到右遍历
sX的每一位数字,尝试把它作为子序列的第k位(k从0到m-1) - 选择时要满足三个核心判断:
- 如果当前选的数字 >
sY[k]:剩下的m - k - 1位直接从当前位置后面的数字里选最小的几个(保持顺序),这样组成的数是当前情况下最小的大于Y的数,直接记录候选 - 如果当前选的数字 ==
sY[k]:要检查当前位置后面的数字能否组成长度为m - k - 1的子序列,且这个子序列大于sY[k+1:];如果可以,就继续往下确定下一位 - 如果当前选的数字 <
sY[k]:直接跳过,因为后续无论怎么选,整个子序列都不可能大于Y
- 如果当前选的数字 >
- 从左到右遍历
- 从所有符合条件的候选中挑出最小的那个,就是我们要的结果。
拿你给的例子来说:X=4186(sX="4186"),Y=11(sY="11"),m=2:
- 第一位尝试选
sX[0]的4:大于sY[0]的1,剩下1位可以选后面最小的1,得到41,但我们要找更小的,所以继续看后面的数字 - 第一位选
sX[1]的1:等于sY[0]的1,接下来检查后面的数字(8、6)能否组成大于sY[1](1)的1位数字——显然可以,然后选后面最小的符合条件的数字6,得到16,这就是最小的大于11的数,也就是最终答案。
三、如果找不到长度为m的子序列,找长度为m+1的最小子序列
如果所有长度为m的子序列都小于等于Y,那我们只能找长度为m+1的最小子序列——因为位数更长的数必然大于Y,且位数越短越接近Y,所以优先选m+1位的。
找长度为k的最小子序列可以用经典的单调栈算法:
- 遍历
sX,维护一个单调递增的栈,保证栈中元素数量不超过k - 对于每个数字,如果栈顶元素大于当前数字,且弹出后剩下的元素数量加上后面未遍历的元素数量足够组成k位,就弹出栈顶,直到满足条件再将当前数字入栈
- 最终栈中的元素就是长度为k的最小子序列(X是正整数,所以不会出现前导0的问题)
比如X=1000,Y=999:所有长度为3的子序列都是000,小于999,这时候找长度为4的最小子序列就是1000,也就是X本身,这就是答案。
四、特殊情况补充
- 如果X和Y位数相同,且X本身就大于Y:要找X的子序列中大于Y的最小数(可能是X本身,也可能是更小的,比如X=4321,Y=1234,那最小的大于Y的同位数子序列就是4321;如果X=132,Y=12,位数不同,就找长度为2的子序列)
- 如果有多个候选结果:比如X=121,Y=11,长度为2的子序列有12、11、21,其中大于11的最小是12,直接选它即可。
备注:内容来源于stack exchange,提问作者Sai Likhith Adari




