贪心算法学习——单调递增的数字

一，单调递增的数字

1.题目

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回小于或等于 n 的最大数字，且数字呈 单调递增 。

示例 1:
输入: n = 10
输出: 9
示例 2:
输入: n = 1234
输出: 1234
示例 3:
输入: n = 332
输出: 299

2.题目接口

class Solution {
public:
    int monotoneIncreasingDigits(int n) {

    }
};

3.解题思路及其代码

暴力法解题步骤：

1.首先用for循环从n开始遍历直到遍历到0.

2.将遍历到的数字转换成字符串(使用to_string)。

3.使用while循环用两个指针指向字符串的前后两位，如果前面的大于后面的字符便break。如果不是便继续移动指针知道到了字符串的结尾。

3.出来时判断一下我的第二个字符串是否指向str.size()位，如果是便返回这个数字。如果不是便继续循环。

代码如下：
class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        for(int i = n;i>=0;i--)
        {
            string str = to_string(i);
            int pre = 0;
            int last = 1;

            while(last<str.size())
            {
                if(str[pre]>str[last])
                {
                    break;
                }

                pre++;
                last++;
            }

            if(last == str.size())
            {
                return  i;
            }
        }

        return -1;

    }
};
但是提交以后会超时：

这就说明我们的思路是对的但是我们的代码还需要改进一下。

贪心解法步骤：

先来举个例子：

n == 1234158，这时我们该输出什么答案呢？经过计算可知答案应该是：1233999

n == 1255516, 这时我们该输出什么答案呢？经过计算可知答案应该是： 1249999

n == 1101, 这时我们该输出什么答案呢？经过计算可知答案应该是： 999

从这些例子可以发现，我们的比n小找到一个最大的递增数字的操作是：

1.先从零下标开始找到最大的递增下标。

2.找到后看看前面有没有连续相等的情况，若有便往前找，找到下标最小连续相等的情况。

3.开始将找到的这个下标减1，再将这个下标后面的数字都变成9.

代码如下：
class Solution {
public:
    int monotoneIncreasingDigits(int n) {
         string str = to_string(n);//将n转换成字符串
         int m = str.size();//计算长度
         int i = 0;

         while(i+1<=m&&str[i]<=str[i+1])i++;//递增便++i.
         if(i+1 == m)//若这个字符完全都是递增的便直接返回
         {
             return stoi(str);
         }

         while(i-1>=0&&str[i-1]==str[i])i--;//若有连续相等的便找到最小下标的那个数

         str[i]--;//改变这个数，若是0便会变成-1，会被舍弃掉减小位数。

         for(int j = i+1;j<m;j++)//将后面的变为9便可以得到最大的递增序列。
         {
             str[j] = '9';
         }

         return stoi(str);//转为数字返回
    }
};
过啦：