Leetcode 2259. Remove Digit From Number to Maximize Result

Remove Digit From Number to Maximize Result"/>

Leetcode 2259. Remove Digit From Number to Maximize Result

题目

解法1：暴力搜索

note：c++中数字组成的字符串可以直接比较大小

class Solution {
public:string removeDigit(string number, char digit) {string max_res = "";for(int i=0;i<number.size();i++){char d = number[i];if(d != digit) continue;string new_num = number.substr(0,i) + number.substr(i+1);if(max_res == "" || new_num > max_res){max_res = new_num;}}return max_res;}
};

解法2:O(n)

这道题的关键在于看某个位置是否该被移除。假设number有n位，现在i位的数字与digit相同，考虑i位移除后的效果。首先对于这个number，不管移除哪一个，数字都会变成n-1位，假设移除不是i的右边的一个位置，那么i现在所在的位置不变。但是相应的如果移除i位，i+1的位置就会成为i之前所在的位置。所以如果i+1的位置数字大于i位的数字，则数字必定比移除其他位要大，则问题转化为：
从左向右便利，第一个number[i+1] > number[i]的位置即是我们寻找的答案，如果没有符合条件的情况，那么就应该移除跟digit相同的最右边的位置

class Solution {
public:string removeDigit(string number, char digit) {int right_most = 0;for(int i=0;i<number.size();i++){if(number[i] == digit){right_most = i;if(number[i] < number[i+1]){return number.substr(0,i) + number.substr(i+1);}}}return number.substr(0,right_most) + number.substr(right_most+1);}
};