题目描述
给你一个表示某个正整数的字符串 number
和一个字符 digit
。
从 number
中 恰好 移除 一个 等于 digit
的字符后,找出并返回按 十进制 表示 最大 的结果字符串。生成的测试用例满足 digit
在 number
中出现至少一次。
样例
输入:number = "123", digit = "3"
输出:"12"
解释:"123" 中只有一个 '3',在移除 '3' 之后,结果为 "12"。
输入:number = "1231", digit = "1"
输出:"231"
解释:可以移除第一个 '1' 得到 "231" 或者移除第二个 '1' 得到 "123"。
由于 231 > 123 ,返回 "231"。
输入:number = "551", digit = "5"
输出:"51"
解释:可以从 "551" 中移除第一个或者第二个 '5'。
两种方案的结果都是 "51"。
限制
2 <= number.length <= 100
number
由数字'1'
到'9'
组成。digit
是'1'
到'9'
中的一个数字。digit
在number
中出现至少一次。
算法
(贪心) $O(n)$
- 从高位开始遍历。
- 如果待移除的数字的低一位比待移除数字 大,则直接移除,算法结束。
- 否则,往后继续寻找待移除的数字,直到满足条件 2 或者是最后一个待移除的数字为止。
时间复杂度
- 遍历字符串一次,故总时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储答案。
C++ 代码
class Solution {
public:
string removeDigit(string number, char digit) {
const int n = number.size();
int p = -1;
for (int i = 0; i < n; i++) {
if (number[i] != digit)
continue;
p = i;
if (digit < number[i + 1])
break;
}
return number.substr(0, p) + number.substr(p + 1);
}
};