代码随想录刷题|LeetCode 738.单调递增的数字 714. 买卖股票的最佳时机含手续费 968.监控二叉树

738.单调递增的数字

题目链接：力扣

思路

        这个题意是很简单的，拿到题目就会有一个思路，就是沿着给定的数字往下判断就可以了，这其实是一种暴力解法，对java语言来说会超出时长。所以应该使用其他方法

        本题要求的是小于等于N的最大单调递增的正数，要明白一种情况：一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]--，然后strNum[i]给为9
        比如：332 ，后面的32是不满足的，那就将2变成9，前面的3减一变成2。
                  成为了329，其实中间的331，330，也都是不满足的
                  此时前面的32也是不满足的，那就将2变成9，前面的3减一变成2.
                  成为了229，其中230-329 都是不满足的

        所以这道题目的局部最优是：遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]--，然后strNum[i]给为9，可以保证这两位变成最大单调递增整数

        全局最优是：得到小于等于N的最大单调递增的整数

        可以从局部最优可以推出全局最优，但是还存在一个问题，那就是对数字的遍历顺序，是从前向后遍历呢，还是从后向前遍历呢

        还是以332为例：
        从前向后遍历，33 是满足条件的，32是不满足条件的，改成29，最终是329，是不可以的，所以从前向后遍历会改变已经遍历过的结果了，就会造成不准确
        从后向前遍历，32是不满足情况的，改成29，为329，接下来，32是不满足情况的，改成29，最终是229，所以从后向前遍历，是可以不断利用上次比较出的结果的

        所以这道题目要想清楚两件事：
                1、贪心思路在哪里：怎么保证局部最优，这个是不好想到的
                2、选择哪种遍历顺序

单调递增的数字

暴力解法(会超出时长)

class Solution {
    public int monotoneIncreasingDigits(int n) {
 
        for (int i = n; i > 0; i--) {
            if (checkNum(i)) {
                return i;
            }           
        }
        return 0;
    }
 
    private boolean checkNum(int num) {
        int max = 10;
        while (num > 0) {
            int t = num % 10;
            if (max >= t) {
                max = t;
            } else {
                return false;
            }
            num = num / 10;
        }
 
        return true;
    }
}

贪心解法

        java中

class Solution {
    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));
 
    }
}

714. 买卖股票的最佳时机含手续费

题目链接：力扣

思路

        二刷再看

买卖股票的最佳时机含手续费

968.监控二叉树

题目链接：力扣

思路

        二刷再看

监控二叉树