力扣738单调递增的数字思路以及贪心总结

力扣上的第738题，大家刚开始看的可能比较懵，读懂之后就会发现其实是找小于n的并且右边位上的数字大于等于左边位上的数字的最大整数。这道题主要考的就是一个思路，刚开始我想了近半个小时，没有丝毫思路，就看了一部分解析，然后得到思路如下：

        从这个数字的各位开始向左依次比较，若左边数大于右边，那么左边数减一，右边数变为九。

        我的第一部分思路就到这里，写完之后测试全部通过，提交的时候测试用例100失败，答案应该是99，我的是90，然后我就很大意的加了个当n是10的整数倍时，直接返回n-1，结果提交的时候测试用例101也错了，这个时候我才意识到问题的严重性，一旦遇到大于等于三位数且中间有零的就会出错。于是我又去看解析，解析中并没有提到如何解决这个问题，然后我直接去参考答案，发现答案中确实有其他步骤，经过我参考之后终于领悟到这道题所有的思路：

        首先将数字n转化成数字型数组，方便操作；然后设置一个正无穷的变量m(当然如果第二个for循环添加一个判断的话，将m设置成合理的数字也可以)；再然后从这个数字的各位开始向左依次比较，若左边数大于右边，那么左边数减一，右边数变为九，记录m为本次索引；最后将从m开始之后的所有数字都变成九，再将数组转成数字即可输出。代码如下

        var monotoneIncreasingDigits = function (n) {
            n = String(n).split('').map(item => +item)//将n转换成以数字型位元素的数组
            let m = Infinity//设置变量m为正无穷
            for (let i = n.length - 1; i > 0; i--) {
                if (n[i - 1] > n[i]) {
                    m = i//使用m记录最近一次改编为9的地方
                    n[i - 1] -= 1
                    n[i] = 9
                }
            }
            for (let i = m; i < n.length; i++) {//将最近改变为九之后的数字全部变成九
                n[i] = 9
            }
            return +n.join('')//返回结果
        };

贪心算法总结：

        其实贪心算法还真的没有什么可以总结的，还是强调贪心算法没有具体的模板，需要的思考比较多；我们可以大胆假设，只要每个部分取最合理，最终结果最合理，没有反例，那么就可以尝试贪心；不要纠结具体推理和数学推导过程，因为这并不在我们思考之内。