leetcode 738 单调递增的数字

以你之姓@ 2022-09-15 13:52 93阅读 0赞

## 前言 ##

题目：[738. 单调递增的数字][738.]

参考题解：[单调递增的数字-代码随想录][-]

--------------------

## 提交代码 ##

### 错误的思路：从高位往低位考虑 ###

我努力想把这个错误的思路，修正过来。但是，没有成功。下面是错误思路的代码。

#include <vector>
    #include <algorithm>
    #include <cmath>
    
    using namespace std;
    
    class Solution {
    public:
        bool maxBehind(int cur, vector<int>& num){ // 在num中，cur位置的元素，是否大于等于cur之后的所有元素
            bool flag = true;
            for(int i=cur+1; i<num.size(); i++){
                if(num[cur]<num[i]){
                    flag = false;
                    break;
                }
            }
            return flag;
        }
    
        int monotoneIncreasingDigits(int n) {
            // 贪心思路：
            // 当前位置比后面所有位置都大；如果该位置不动，后面位置无论如何变化，都不可能调整成单调递增;所以将该位置后面的数字清零，再减一
            // 当前位置没有比后面所有位置都到，当前位置保留，后面自调整，使得单调递增。
    
            // 贪心思路，错误。反例：102
            // 错误原因，1虽然没有比后面的都大，但是后面不足以调整使得单调递增
    
            // 修正方法，必须保证紧邻1后面的那个数字大于1才行,这样后面才有修正能力。
            // 比如120。2大于1，有能力减一，保底保证2后面全为9
    
            // 修正方法，又有问题。比如1120。第一个1，无法跳过第二个1，得知后面有2来保证升序
    
            int result = 0;
    
            // 将n每位提取出来，放入num中
            vector<int> num; 
            if(n==0)
                num.push_back(0);
            else{
                while(n>0){
                    num.push_back(n%10);
                    n = n/10;
                }
            }
            reverse(num.begin(),num.end());
    
            for(int i=0; i<num.size(); i++){
                if(i==num.size()-1) // 最后一位不需要花里胡哨，直接保留
                    result += num[i];
                else if(maxBehind(i,num)){ // cur位置的元素，大于等于cur之后的所有元素：直接将尾数置零，并减一
                    result += (num[i]*pow(10,num.size()-i-1)-1);
                    break;
                }else if(num[i+1]>num[i]){ // 保留当前元素不变
                    result += num[i]*pow(10,num.size()-i-1);
                }
            }
    
            return result;
        }
    };

### 正确思路：从低位往高位考虑 ###

转变下思路，从低位往高位考虑。低位小于高位，将低位变成9，高位减一。

so easy.

class Solution {
    public:
        int monotoneIncreasingDigits(int n) {
            // 将n每位提取出来，放入num中; 注意，存入vector中的顺序是倒着的
            vector<int> num; 
            if(n==0)
                num.push_back(0);
            else{
                while(n>0){
                    num.push_back(n%10);
                    n = n/10;
                }
            }
            
            for(int i=0; i<num.size()-1; i++){ // 按照个位，十位，百位顺序比较
                if(num[i] >= num[i+1]) // 右边位等于等于左边位
                    continue;
                else{
                    int j=i;
                    while(j>=0){
                        num[j]=9;
                        j--;
                    }
                    num[i+1]=num[i+1]-1;
                }
            }
    
            int result = 0;
            for(int i=0; i<num.size(); i++){
                result += num[i]*pow(10,i);
            }
    
            return result;
        }
    };

参考题解也是这个思路。但是它的代码要简洁很多。

下面代码来自参考题解。

class Solution {
    public:
        int monotoneIncreasingDigits(int N) {
            string strNum = to_string(N);
            // flag用来标记赋值9从哪里开始
            // 设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行
            int flag = strNum.size();
            for (int i = strNum.size() - 1; i > 0; i--) {
                if (strNum[i - 1] > strNum[i] ) {
                    flag = i;
                    strNum[i - 1]--;
                }
            }
            for (int i = flag; i < strNum.size(); i++) {
                strNum[i] = '9';
            }
            return stoi(strNum);
        }
    };

[738.]: https://leetcode-cn.com/problems/monotone-increasing-digits/
[-]: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0738.%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5%AD%97.md