代码随想录算法训练营第三十天 | leetcode：单调递增的数字,贪心算法总结

_zzh 的个人博客 / 31 / 0 / 创建于 1个月前 / 更新于 1个月前

738. 单调递增的数字

注意的地方

int类型使用strval(n)转换为string类型str后，使用数组方式获取str[i],不能使用自增自减操作str[i]++ , str[i]–，以及 str[i] -= str[i], str[i] += str[i]；
使用字符串处理后，返回需要intval($str)转回int型，否则会出现返回“09”的情况，导致解答错误。
99这种相等的数也属于单调递增

解题方法

原理：从后往前遍历，如果遇到不是单调递增的数，则把前一位数（i-1） - 1操作(例如：90，变成80),同时标记i的位置，把i及之后的数字，都赋值为9。最后变成89。

从后往前遍历字符串，如果str[i-1] > str[i]（非单调递增）, 则把str[i-1] - 1, 同时使用flag标记当前处理位置i。
从flag位置开始处理字符串，把flag及之后的数字都赋值为9。

复杂度

时间复杂度

O(n)

空间复杂度

O(n)

code

class Solution {
    /**
     * @param Integer $n
     * @return Integer
     */
    function monotoneIncreasingDigits($n) {
        //转换字符串
        $str = strval($n);
        $flag = $len = strlen($str);
        for($i = $len - 1; $i > 0; $i--){
            //判断非递增
            if($str[$i-1] > $str[$i]){
                //处理i-1
                $str[$i-1] = $str[$i-1] - 1;
                //flag标记当前位置i
                $flag = $i;
            }
        }
        //处理flag及之后的数字都赋值为9
        for($i = $flag; $i < $len; $i++){
            $str[$i] = "9";
        }
        //转换为int返回
        return intval($str);
    }
}

贪心算法的一些总结

贪心算法简单程度题型的解题核心往往就是生活常识，难点在于怎么把我们的常识应用到程序里面，如何把过程用程序模拟出来。例如：分发饼干，柠檬水找零，甚至是加油站，这些不考虑程序的情况下，就是常识问题。
也有很多题目不那么“常识”。解法往往很妙，比如摆动序列，把摆动模拟成上坡下坡，取头尾+上下顶峰的操作；两个维度权衡问题：分发糖果，根据身高重建队列，这种问题第一眼看上去非常难处理，但是遵循一边处理完再处理另一边的原则，就会发现不仅思路清晰，困难题目也不过如此。还有就是重叠区间：用最少数量的箭引爆气球，划分字母区间，合并区间，无重叠区间，这类题目是我觉得贪心算法里唯一算是有套路的题型，基本都是先排序，在判断重叠区间，更新左边界或者右边界，处理重叠的逻辑或者不重叠的逻辑。主要难点就是在更新边界的处理。但是以上题目往往比较难想出这种解法，但是一旦知道解法后，都会忍不住发出感叹：“妙啊！”
相对的对个人而言，贪心算法也有很难理解的题型：跳跃游戏。跳跃游戏类的题型，哪怕看了解题过程，也会觉得很抽象。至今都还是有点云里雾里。
具体什么叫贪心，卡哥的总结：如果找出局部最优并可以推出全局最优，就是贪心，如果局部最优都没找出来，就不是贪心，可能是单纯的模拟。