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.监控二叉树
题目链接：力扣
思路
二刷再看
