2259-移除指定数字得到的最大结果
给你一个表示某个正整数的字符串 number
和一个字符 digit
。
从 number
中 恰好 移除 一个 等于 digit
的字符后,找出并返回按 十进制 表示 最大
的结果字符串。生成的测试用例满足 digit
在 number
中出现至少一次。
示例 1:
**输入:** number = "123", digit = "3"
**输出:** "12"
**解释:** "123" 中只有一个 '3' ,在移除 '3' 之后,结果为 "12" 。
示例 2:
**输入:** number = "1231", digit = "1"
**输出:** "231"
**解释:** 可以移除第一个 '1' 得到 "231" 或者移除第二个 '1' 得到 "123" 。
由于 231 > 123 ,返回 "231" 。
示例 3:
**输入:** number = "551", digit = "5"
**输出:** "51"
**解释:** 可以从 "551" 中移除第一个或者第二个 '5' 。
两种方案的结果都是 "51" 。
提示:
2 <= number.length <= 100
number
由数字'1'
到'9'
组成digit
是'1'
到'9'
中的一个数字digit
在number
中出现至少一次
方法一:枚举移除下标
思路与算法
我们可以遍历 number 寻找所有可以移除的下标。同时我们用字符串 res 记录可以得到的最大结果。res 初始为空字符串。每当我们找到 number}[i] = \textit{digit 的下标 i,我们构造移除下标 i 后的字符串 tmp。由于移除下标后字符串的长度一定相等,因此字典序的大小关系等于对应数值的大小关系。同时由于空字符串在字典序中小于任何非空字符串,我们只需要令 res 等于 res 与 tmp 的较大值即可。最终,我们返回 res 作为答案。
代码
1 | class Solution { |
1 | class Solution: |
复杂度分析
时间复杂度:O(n^2),其中 n 为 number 的长度。我们至多需要移除 O(n) 次字符串,每次生成移除后字符串并比较的时间复杂度为 O(n)。
空间复杂度:O(n),即为生成移除后字符串时辅助字符串的空间开销。
方法二:贪心
提示 1
按照以下策略移除数字可以使得最终结果最大:
我们从左至右遍历 number,如果遍历到 number}[i] = \textit{digit,且 number}[i] < \textit{number}[i + 1](如果存在,下同),则我们删除该字符后得到的结果最大;
如果遍历完成依旧不存在满足上一个条件的下标,则我们删除 digit 出现的最后一个下标,此时删除该字符后得到的结果最大。
提示 1 解释
我们可以以条件 2 得到的数 num 作为基准,并将其与其它可能得到的结果进行比较。
首先,如果移除的位数 i 更靠前,移除后的结果与 num 之差的绝对值一定更高。
其次,我们根据 number}[i] 与 number}[i + 1] 的大小关系分类讨论:
number}[i] < \textit{number}[i + 1],此时删除后的结果一定大于 num,且大于删除后面所有位置得到的结果。
number}[i] = \textit{number}[i + 1],此时删除 number}[i] 与删除 number}[i + 1] 得到的结果相同;
number}[i] > \textit{number}[i + 1],此时删除后的结果一定小于 num,因此我们不能删除该元素。
综上,提示 1 中的方法一定可以使得最终结果最大。
思路与算法
我们可以根据 提示 1 找到最佳的删除下标。
具体地,我们从左至右遍历 为 number,并用 last 记录最近遍历到的可以删除的下标。如果遍历到 number}[i] = \textit{digit时,我们将 last 更新为 i。如果还满足 number}[i] < \textit{number}[i + 1],则我们返回删除该字符得到的结果作为答案。
如果遍历完成后仍未找到符合上述要求的下标,则我们删除 last 下标对应的字符并返回。
代码
1 | class Solution { |
1 | class Solution: |
复杂度分析
时间复杂度:O(n),其中 n 为 number 的长度。即为寻找最佳移除位置和构造移除后字符串的时间复杂度。
空间复杂度:O(n),即为生成移除后字符串时辅助字符串的空间开销。