代码随想录算法训练营第三十七天｜738.单调递增的数字 968.监控二叉树 总结

 738.单调递增的数字 

代码随想录

例如：98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]--，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。

从前向后遍历的话，遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]减一，但此时如果strNum[i - 1]减一了，可能又小于strNum[i - 2]。

这么说有点抽象，举个例子，数字：332，从前向后遍历的话，那么就把变成了329，此时2又小于了第一位的3了，真正的结果应该是299。

那么从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332 -> 329 -> 299
 

public int monotoneIncreasingDigits(int n) {
        String s = String.valueOf(n);
        char[] chars = s.toCharArray();
        int start = s.length();
        for (int i = s.length() - 2; i >= 0; i--) {
            if (chars[i] > chars[i + 1]) {
                chars[i]--;
                start = i+1;
            }
        }
        for (int i = start; i < s.length(); i++) {
            chars[i] = '9';
        }
        return Integer.parseInt(String.valueOf(chars));
    }

 968.监控二叉树 （可以跳过）

本题是贪心和二叉树的一个结合，比较难，一刷大家就跳过吧。 

代码随想录

 总结 

可以看看贪心算法的总结，贪心本来就没啥规律，能写出个总结篇真的不容易了。 

代码随想录

贪心简单题

以下三道题目就是简单题，大家会发现贪心感觉就是常识。是的，如下三道题目，就是靠常识，但我都具体分析了局部最优是什么，全局最优是什么，贪心也要贪的有理有据！

• 贪心算法：分发饼干(opens new window)
• 贪心算法：K次取反后最大化的数组和(opens new window)
• 贪心算法：柠檬水找零(opens new window)

#贪心中等题

贪心中等题，靠常识可能就有点想不出来了。开始初现贪心算法的难度与巧妙之处。

• 贪心算法：摆动序列(opens new window)
• 贪心算法：单调递增的数字(opens new window)

#贪心解决股票问题

大家都知道股票系列问题是动规的专长，其实用贪心也可以解决，而且还不止就这两道题目，但这两道比较典型，我就拿来单独说一说

• 贪心算法：买卖股票的最佳时机II(opens new window)
• 贪心算法：买卖股票的最佳时机含手续费 (opens new window)本题使用贪心算法比较绕，建议后面学习动态规划章节的时候，理解动规就好

#两个维度权衡问题

在出现两个维度相互影响的情况时，两边一起考虑一定会顾此失彼，要先确定一个维度，再确定另一个一个维度。

• 贪心算法：分发糖果(opens new window)
• 贪心算法：根据身高重建队列(opens new window)

在讲解本题的过程中，还强调了编程语言的重要性，模拟插队的时候，使用C++中的list（链表）替代了vector(动态数组)，效率会高很多。

所以在贪心算法：根据身高重建队列（续集） (opens new window)详细讲解了，为什么用list（链表）更快！

贪心难题

这里的题目如果没有接触过，其实是很难想到的，甚至接触过，也一时想不出来，所以题目不要做一遍，要多练！

#贪心解决区间问题

关于区间问题，大家应该印象深刻，有一周我们专门讲解的区间问题，各种覆盖各种去重。

• 贪心算法：跳跃游戏(opens new window)
• 贪心算法：跳跃游戏II(opens new window)
• 贪心算法：用最少数量的箭引爆气球(opens new window)
• 贪心算法：无重叠区间(opens new window)
• 贪心算法：划分字母区间(opens new window)
• 贪心算法：合并区间(opens new window)

#其他难题

贪心算法：最大子序和 (opens new window)其实是动态规划的题目，但贪心性能更优，很多同学也是第一次发现贪心能比动规更优的题目。

贪心算法：加油站 (opens new window)可能以为是一道模拟题，但就算模拟其实也不简单，需要把while用的很娴熟。但其实是可以使用贪心给时间复杂度降低一个数量级。

最后贪心系列压轴题目贪心算法：我要监控二叉树！ (opens new window)，不仅贪心的思路不好想，而且需要对二叉树的操作特别娴熟，这就是典型的交叉类难题了。