贪心思想 核心：从局部最优到全局最优
解题步骤
将问题分解为若干个子问题
找出适合的贪心策略
求解每一个子问题的最优解
将局部最优解堆叠成全局最优解
找出局部的最优解，从而推出全局最优解
两个贪心思路：
大饼干喂大胃口 或者 小饼干喂小胃口
自己的解法：贪心 + 排序 + 双指针
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public int findContentChildren (int [] g, int [] s) { Arrays.sort(g); Arrays.sort(s); int count = 0 ; for (int i = 0 , j = 0 ; i < g.length && j < s.length;) { if (s[j] >= g[i]) { count++; j++; i++; } else { j++; } } return count; } }
其他解法：贪心 + 排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution { public int findContentChildren (int [] g, int [] s) { Arrays.sort(g); Arrays.sort(s); int start = 0 ; int count = 0 ; for (int i = 0 ; i < s.length && start < g.length; i++) { if (s[i] >= g[start]) { start++; count++; } } return count; } public int findContentChildren (int [] g, int [] s) { Arrays.sort(g); Arrays.sort(s); int count = 0 ; int start = s.length - 1 ; for (int index = g.length - 1 ; index >= 0 ; index--) { if (start >= 0 && g[index] <= s[start]) { start--; count++; } } return count; } }
贪心思想：（假装）删除单调坡度上的节点从而使得局部峰值++
需要分三种情况：
上下坡中有平坡
添加 preDiff = 0 即可解决问题
数组首尾两端 题目要求如果只有两个元素，且两个元素不想等，此时长度为2。
解决方法：补全开头的元素 -> preDiff 初始值为0
单调坡中有平坡
此时结果应为2不为3，如果我们按照以下的代码更新 preDiff就会出现问题，因为此时preDiff直接，实时地更新为curDiff：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution {public : int wiggleMaxLength (vector<int >& nums) { if (nums.size() <= 1 ) return nums.size(); int curDiff = 0 ; int preDiff = 0 ; int result = 1 ; for (int i = 0 ; i < nums.size() - 1 ; i++) { curDiff = nums[i + 1 ] - nums[i]; if ((preDiff <= 0 && curDiff > 0 ) || (preDiff >= 0 && curDiff < 0 )) { result++; } preDiff = curDiff; } return result; } };
解决方法：preDiff当且仅当摆动时才更新
结论 综上我们有：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public int wiggleMaxLength (int [] nums) { int preDiff = 0 ; int curDiff = 0 ; int result = 1 ; for (int i = 0 ; i < nums.length - 1 ; i++) { curDiff = nums[i + 1 ] - nums[i]; if (checkWiggle(preDiff, curDiff)) { result++; preDiff = curDiff; } } return result; } private boolean checkWiggle (int preDiff, int curDiff) { if (preDiff >= 0 && curDiff < 0 || preDiff <= 0 && curDiff > 0 ) { return true ; } return false ; } }
PS:本题也可以使用动态规划：（当前仅了解，tbc…）
设 dp 状态dp[i][0]，表示考虑前 i 个数，第 i 个数作为山峰的摆动子序列的最长长度
设 dp 状态dp[i][1]，表示考虑前 i 个数，第 i 个数作为山谷的摆动子序列的最长长度
转移方程为：
dp[i][0] = max(dp[i][0], dp[j][1] + 1)，其中0 < j < i且nums[j] < nums[i]，表示将 nums[i]接到前面某个山谷后面，作为山峰。dp[i][1] = max(dp[i][1], dp[j][0] + 1)，其中0 < j < i且nums[j] > nums[i]，表示将 nums[i]接到前面某个山峰后面，作为山谷。
贪心 连续和 + 当前数，如果连续和 < 0 那么直接取当前数作为新的开始。因为连续和<0必定会拖累当前数的值
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution { public int maxSubArray (int [] nums) { int result = Integer.MIN_VALUE; int count = 0 ; for (int i = 0 ; i < nums.length; i++) { int curNum = nums[i]; count += curNum; if (count > result) result = count; if (count < 0 ) count = 0 ; } return result; } }
本题的贪心用法在于一个数学思想：
比如我们需要计算第三天卖出第零天买入能够产生的利润，那么就是 profit[3] - profit[0]. 巧妙的利用下数学性质：
profit[3] - profit[0] = proft[3] - profit[2] + profit[2] - profit[1] + profit[1] - profit[0]
也就是每一天的利润差额。
因此：
因此我们只需要收集两天股票差额为正数的利润就可以拿到最终全局的一个最大利润，即局部最优到全局最优。
1 2 3 4 5 6 7 8 9 10 class Solution { public int maxProfit (int [] prices) { int sum = 0 ; for (int i = 1 ; i < prices.length; i++) { int curProfit = prices[i] - prices[i - 1 ]; if (curProfit > 0 ) sum += curProfit; } return sum; } }
首先我们不需要实际的知道要跳到哪里，我们只需要知道覆盖范围即可，因为在这个最大范围中，不管怎么跳都可以跳到。
因此检查覆盖范围是否包含终点就是我们要的结果。
贪心思想：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点 。
1 2 3 4 5 6 7 8 9 10 11 12 class Solution { public boolean canJump (int [] nums) { int cover = 0 ; if (nums.length == 1 ) return true ; for (int i = 0 ; i <= cover; i++) { cover = Math.max(cover, nums[i] + i); if (cover >= nums.length - 1 ) return true ; } return false ; } }
和上一道题的区别在于，此题需要计算能够到终点的步数。因此在继承了上一步的 覆盖范围 的思路上我们需要知道什么时候把返回值增加。
覆盖范围不变，当index到了当前能覆盖的最远距离时，返回值增加。因为当前覆盖的范围是无论如何都能达到的。
贪心思想：覆盖范围最大，使用的步数最少。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public int jump (int [] nums) { int curCover = 0 , nextCover = 0 ; int count = 0 ; if (nums.length == 1 ) return count; for (int i = 0 ; i < nums.length; i++) { nextCover = Math.max(nextCover, i + nums[i]); if (i == curCover) { count++; curCover = nextCover; if (nextCover >= nums.length - 1 ) break ; } } return count; } }
贪心 + 分情况讨论
取反一个负数会使得结果变大，取反正数会使结果变小，取反 0 值对结果没有影响
如果想要把 nums[i] 替换为 -nums[i] 并且想要得到可能的最大和。那么我们应该尽量：
更改负数，将负数变为正数
将正数的值小的数变为负数从而减少影响。
因此需要按照绝对值的大小来进行降序排序。然后优先更改负数。如果k<负数个数的情况直接返回结果，但如果 K 的值较大，那么我们不得不去修改非负数（即正数或者 0）了：
如果数组中存在 0，那么我们可以对它进行多次修改，直到把剩余的修改次数用完；
如果数组中不存在 0 并且剩余的修改次数是偶数，由于对同一个数修改两次等价于不进行修改，因此我们也可以在不减小数组的和的前提下，把修改次数用完；
如果数组中不存在 0 并且剩余的修改次数是奇数，那么我们必然需要使用单独的一次修改将一个正数变为负数（剩余的修改次数为偶数，就不会减小数组的和）。为了使得数组的和尽可能大，我们就选择那个最小的正数。
这道题可以用计数排序 来优化（June 9th： 还在学习计数排序）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int largestSumAfterKNegations (int [] nums, int k) { Integer[] numsInt = Arrays.stream(nums).boxed().toArray(Integer[]::new ); Arrays.sort(numsInt, (a, b) -> Math.abs(b) - Math.abs(a)); int idx = 0 ; while (idx < numsInt.length && k > 0 ) { if (numsInt[idx] < 0 ) { numsInt[idx] = -numsInt[idx]; k--; } idx++; } if (k % 2 == 1 ) numsInt[numsInt.length - 1 ] = -numsInt[numsInt.length - 1 ]; int result = 0 ; for (int a : numsInt) result += a; return result; } }
这道题的思路有点像跳跃游戏，同样需要看覆盖范围。
若总油量 > 总消耗，那么一定有办法绕一圈
记录一个curSum来跟踪当前油量和，如果curSum < 0那么说明之前无论怎么走都无法达到当前的点i，因此从下一个点开始找，并且重置curSum
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int canCompleteCircuit (int [] gas, int [] cost) { int curSum = 0 ; int start = 0 ; int totalSum = 0 ; int len = gas.length; for (int i = 0 ; i < len; i++) { curSum += gas[i] - cost[i]; totalSum += gas[i] - cost[i]; if (curSum < 0 ) { curSum = 0 ; start = i + 1 ; } } if (totalSum < 0 ) return -1 ; return start; } }
左右扫描两次 + 贪心
单从左向右扫描就会导致单调递减的情况下出错，因此我们需要再从右向左扫描一遍。
贪心：
取最大值从而满足当前的孩子的糖比左和右都大，从而满足题目条件
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public int candy (int [] ratings) { int [] candies = new int [ratings.length]; candies[0 ] = 1 ; for (int i = 1 ; i < ratings.length; i++) { if (ratings[i] > ratings[i - 1 ]) { candies[i] = candies[i - 1 ] + 1 ; } else { candies[i] = 1 ; } } int ret = 0 ; for (int i = ratings.length - 1 ; i >= 1 ; i--) { if (ratings[i - 1 ] > ratings[i]) { candies[i - 1 ] = Math.max(candies[i - 1 ], candies[i] + 1 ); } ret += candies[i]; } ret += candies[0 ]; return ret; } }
分类讨论 + 贪心
顾客只可能给你三个面值的钞票，而且我们一开始没有任何钞票，因此我们拥有的钞票面值只可能是 5 美元，10 美元和 20 美元三种
所以会有以下的情况：
5 美元，由于柠檬水的价格也为 5 美元，因此我们直接收下即可。
10 美元，我们需要找回 5 美元，如果没有 5 美元面值的钞票，则无法正确找零。
20 美元，我们需要找回 15 美元，此时有两种组合方式，一种是一张 10 美元和 5 美元的钞票，一种是 3 张 5 美元的钞票，如果两种组合方式都没有，则无法正确找零。当可以正确找零时，两种找零的方式中我们更倾向于第一种，即如果存在 5 美元和 10 美元，我们就按第一种方式找零，否则按第二种方式找零，因为需要使用 5 美元的找零场景会比需要使用 10 美元的找零场景多，我们需要尽可能保留 5 美元的钞票。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public boolean lemonadeChange (int [] bills) { int [] count = new int [3 ]; for (int i = 0 ; i < bills.length; i++) { if (bills[i] == 5 ) { count[0 ]++; } else if (bills[i] == 10 ) { count[0 ] -= 1 ; if (count[0 ] < 0 ) return false ; count[1 ]++; } else { if (count[1 ] > 0 ) { count[1 ] -= 1 ; count[0 ] -= 1 ; if (count[0 ] < 0 ) return false ; } else { count[0 ] -= 3 ; if (count[0 ] < 0 ) return false ; } count[2 ]++; } } return true ; } }
这道题类似于分糖果（135），有两个纬度需要考虑，但是一样的，我们一次只考虑一个。
若考虑K维度：
按照k从小到大，当相等时h从小到大
排序的结果一条都不满足，一个纬度都确定不下来
若考虑H维度：
按照H从高到低，当相等时K从低到高，这样的身高相对顺序是被确定了的
因此我们考虑确定H维度：
优先按身高高的people的k来插入。插入操作过后的people满足队列属性 这是因为按照身高排序之后，优先按身高高的people的k来插入，后序插入节点也不会影响前面已经插入的节点，最终按照k的规则完成了队列。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public int [][] reconstructQueue(int [][] people) { Arrays.sort(people, new Comparator <int []>(){ @Override public int compare (int [] person1, int [] person2) { if (person1[0 ] != person2[0 ]) { return person2[0 ] - person1[0 ]; } else { return person1[1 ] - person2[1 ]; } } }); LinkedList<int []> ret = new LinkedList <>(); for (int i = 0 ; i < people.length; i++) { int [] person = people[i]; int position = person[1 ]; ret.add(position, person); } return ret.toArray(new int [people.length][2 ]); } }
区间调度，重叠类问题 什么是区间调度问题 “区间调度”是一类常见的计算机科学问题，其主要目标是在给定一组区间时，找出最多的不相交区间。在这个问题中，区间通常以一对数字表示，例如 [a, b)，表示一个区间从 a 开始，到 b 结束。
具体的问题定义如下：
给定一个区间的集合，每个区间包括一个开始时间和一个结束时间。编写一个算法，找到最大的不相交区间的集合，即在这个集合中，任何两个区间都不会重叠。
例如，假设我们有以下区间：[1, 2], [2, 3], [3, 4], [1, 3]。最大的不相交区间的集合是 [1, 2], [2, 3], [3, 4]，因为我们可以安排这些区间，使得没有任何两个区间是重叠的。
注意，在解决这类问题时，一个常用的策略是贪心算法。我们首先将所有区间按照结束时间排序，然后每次选择结束时间最早的区间，并且这个区间不与已选择的区间重叠。这种方法能够确保我们总是选择最多的不相交区间。
具体思路 对于区间调度问题，我们考虑如下的贪心思路：
每次选择可选区间中开始最早的那个
每次选择可选区间中最短的那个
选择出现冲突最少的那个区间
但是这些都不对，以下是反例：
每次选择可选区间中开始最早的：
对于区间集合 = [[1,9], [2,5], [6,8]]
应该返回的结果是2，因为可以选中两个区间，即[2,5]和[6,8]。
但如果使用这种策略，实际返回的结果是1，因为它首先选择了开始最早的区间[1,9]，而错过了后面的两个区间。
每次选择最短的区间：
对于区间集合 = [[1,3], [2,4], [5,7], [6,9]]
应该返回的结果是2，因为可以选择两个不相交的区间，例如[1,3]和[5,7]或者[2,4]和[6,9]。
但如果使用这种策略，实际返回的结果是3，它选中了[1,3]，[2,4]和[6,9]，但其中[1,3]和[2,4]是冲突的。
每次选择出现冲突最少的区间：
对于区间集合 = [[1,4], [2,3], [5,6]]
应该返回的结果是2，因为可以选择两个不相交的区间，即[1,4]和[5,6]。
但如果使用这种策略，实际返回的结果是2，选中的区间是[2,3]和[5,6]，虽然结果数量是对的，但选中的区间并不是最优的，因为选择[1,4]和[5,6]可以覆盖更大的区域。
所以，上述的三种贪心策略都不能保证得到最优答案。正确的贪心策略应该是：每次选择结尾最早的，且与当前已选区间不冲突的区间。
实现上可以分为以下三步：
从排序好的（按照结束时间升序排列）选择区间右节点xEnd
把与xEnd相交的区间删除（skip）
重复直至结束
为什么选择区间右端点？
由于我们事先排了序 ，不难发现所有与 x 相交的区间必然会与 x 的 end 相交；如果一个区间不想与 x 的 end 相交，它的 start 必须要大于（或等于）x 的 end：
核心在于：
如果最多有 n 个不重叠的区间，那么就至少需要 n 个箭头穿透所有区间
两个边界挨着的时候也可以使气球引爆
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Solution { public int findMinArrowShots (int [][] points) { Arrays.sort(points, new Comparator <int []>(){ @Override public int compare (int [] point1, int [] point2) { if (point1[1 ] > point2[1 ]) { return 1 ; } else if (point1[1 ] < point2[1 ]) { return -1 ; } else { return 0 ; } } }); int res = findIntervals(points); return res; } private int findIntervals (int [][] points) { int xEnd = points[0 ][1 ]; int count = 1 ; for (int [] point : points) { int start = point[0 ]; if (start > xEnd) { count++; xEnd = point[1 ]; } } return count; } }
找到最多不会重复的区间，原长度剪去就是剩下的至少需要去除的区间
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution { public int eraseOverlapIntervals (int [][] intervals) { Arrays.sort(intervals, new Comparator <int []>(){ @Override public int compare (int [] interval1, int [] interval2) { if (interval1[1 ] > interval2[1 ]) { return 1 ; } else if (interval1[1 ] < interval2[1 ]) { return -1 ; } else { return 0 ; } } }); int noOverlappingCount = findNotOverlaps(intervals); return intervals.length - noOverlappingCount; } private int findNotOverlaps (int [][] intervals) { int end = intervals[0 ][1 ]; int count = 1 ; for (int [] interval : intervals) { int start = interval[0 ]; if (start >= end) { end = interval[1 ]; count++; } } return count; } }
找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public List<Integer> partitionLabels (String s) { int [] charPositions = new int [27 ]; for (int i = 0 ; i < s.length(); i++) { charPositions[s.charAt(i) - 'a' ] = i; } int left = 0 , right = 0 ; List<Integer> res = new ArrayList <>(); for (int i = 0 ; i < s.length(); i++) { char c = s.charAt(i); right = Math.max(charPositions[c - 'a' ], right); if (i == right) { res.add(right - left + 1 ); left = i + 1 ; } } return res; } }
按照右端点排序非常的麻烦，因为会出现：
[[2,3],[4,5],[6,7],[8,9],[1,10]]
这个样例需要返回 [1,10]，如果使用正常的正序遍历：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 class Solution { public int [][] merge(int [][] intervals) { Arrays.sort(intervals, new Comparator <int []>() { @Override public int compare (int [] arr1, int [] arr2) { if (arr1[1 ] > arr2[1 ]) { return 1 ; } else if (arr1[1 ] == arr2[1 ]) { return 0 ; } else { return -1 ; } } }); List<int []> ret = new ArrayList <>(); ret.add(intervals[0 ]); for (int i = 1 ; i < intervals.length; i++) { int prevLeft = intervals[i - 1 ][0 ], prevRight = intervals[i - 1 ][1 ]; int left = intervals[i][0 ], right = intervals[i][1 ]; if (left <= prevRight) { int [] removed = ret.remove(ret.size() - 1 ); if (prevLeft > left) { ret.add(intervals[i]); } else { removed[1 ] = right; ret.add(removed); } } else { ret.add(intervals[i]); } } int [][] retArr = new int [ret.size()][2 ]; for (int i = 0 ; i < ret.size(); i++) { retArr[i] = ret.get(i); } return retArr; } }
那么会返回结果:
[[2,3],[4,5],[6,7],[1,10]]
所以我们需要倒序遍历，并将需要加入的不能合并的区间加入链表头，每一次取表头来和当前区间比较是否需要合并，递归处理。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 class Solution { public int [][] merge(int [][] intervals) { Arrays.sort(intervals, new Comparator <int []>() { @Override public int compare (int [] arr1, int [] arr2) { if (arr1[1 ] > arr2[1 ]) { return 1 ; } else if (arr1[1 ] == arr2[1 ]) { return 0 ; } else { return -1 ; } } }); LinkedList<int []> ret = new LinkedList <>(); for (int i = intervals.length - 1 ; i >= 0 ; i--) { if (ret.isEmpty()) { ret.addFirst(intervals[i]); continue ; } int [] last = ret.getFirst(); int prevLeft = last[0 ], prevRight = last[1 ]; int left = intervals[i][0 ], right = intervals[i][1 ]; if (right >= prevLeft) { last[0 ] = Math.min(prevLeft, left); last[1 ] = Math.max(prevRight, right); } else { ret.addFirst(intervals[i]); } } int [][] retArr = new int [ret.size()][2 ]; for (int i = 0 ; i < ret.size(); i++) { retArr[i] = ret.get(i); } return retArr; } }
按照左端点升序排列后右端点按照降序排列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution { public int removeCoveredIntervals (int [][] intervals) { Arrays.sort(intervals, new Comparator <int []>() { @Override public int compare (int [] arr1, int [] arr2) { if (arr1[0 ] > arr2[0 ]) { return 1 ; } else if (arr1[0 ] < arr2[0 ]) { return -1 ; } else { return arr2[1 ] - arr1[1 ]; } } }); int count = 0 ; int left = intervals[0 ][0 ], right = intervals[0 ][1 ]; for (int i = 1 ; i < intervals.length; i++) { int curLeft = intervals[i][0 ], curRight = intervals[i][1 ]; if (left <= curLeft && right >= curRight) { count++; } else if (right >= curLeft && right < curRight) { right = curRight; } else if (curLeft > left && curRight > right) { left = curLeft; right = curRight; } } return intervals.length - count; } }
分情况分析讨论题
这道题按照区间的重合可以区分为以下四种情况：
设两个列表的每个区间为 [an, an+1] [bn, bn+1]，那么如果这两个区间有交集，需满足 b2 >= a1 && a2 >= b1，分下面四种情况：
如果有交集[c1,c2]那么我们有 c1 = max(a1, b1), c2 = min(a2, b2)
那么剩下的就是双指针问题了，当一个区间被作为交集使用过后，即，他是左边的区间时，指针移动
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int [][] intervalIntersection(int [][] firstList, int [][] secondList) { int firstIdx = 0 , secondIdx = 0 ; LinkedList<int []> res = new LinkedList <>(); while (firstIdx < firstList.length && secondIdx < secondList.length) { int a1 = firstList[firstIdx][0 ], a2 = firstList[firstIdx][1 ]; int b1 = secondList[secondIdx][0 ], b2 = secondList[secondIdx][1 ]; if (b1 <= a2 && b2 >= a1) { int c1 = Math.max(a1, b1), c2 = Math.min(a2, b2); res.add(new int []{c1, c2}); } if (a2 < b2) { firstIdx++; } else { secondIdx++; } } return res.toArray(new int [res.size()][]); } }
总结 对于区间调度问题，按照右端点排序的贪心思路解决。对于区间合并问题，按照左端点排序
按照左端点排序的目的是为了保证左端点的前后关系，这样我们就能保证一个区间的左端点一定不会大于其后面区间的左端点。这在处理一些需要关注区间的覆盖，或者合并等问题时会比较有用。
按照右端点排序的目的则是为了保证右端点的前后关系，使得一个区间的右端点不会大于其后面区间的右端点。这在处理一些需要关注区间的交叉，或者选择不重叠区间 的问题时会比较有用。
这道题与其说是一道贪心题，它更像是一道按照规则的模拟题。贪心思想题现在了按照规则构造时候的模拟题
先把数字转化成一个char[]
我们对每一位进行贪心地修改：
由于我们想要数尽可能的大，所以我们要尽可能填充9，而填充9的位置就是第一个单调递减的位置：
12321 -> 12999
3就是第一个需要变化的位置
但是会有一种情况：
1233321 -> 那么这个时候我们就不能只简单的看n 和 n+1我们需要一个额外的变量来跟踪第一个max index：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public int monotoneIncreasingDigits (int n) { char [] nToChar = (n + "" ).toCharArray(); int max = -1 , idx = -1 ; for (int i = 0 ; i < nToChar.length - 1 ; i++) { if (max < nToChar[i]) { max = nToChar[i]; idx = i; } if (nToChar[i] > nToChar[i + 1 ]) { nToChar[idx] -= 1 ; for (int j = idx + 1 ; j < nToChar.length; j++) { nToChar[j] = '9' ; } break ; } } return Integer.parseInt(new String (nToChar)); } }
这是一道带有贪心思想的脑筋急转弯题，需要画图以及理解任务的调度：
贪心体现在：尽可能安排出现次数多的任务，然后将其他任务填充在次数多的任务的冷却期中。
假设我们有桶子：
我们需要执行4个任务，那么由于除了最后一个以外都有冷冻期，那么就会有：
(n + 1) * (m - 1) + 1
假设任务重复次数最多为max，若有tot个任务数量为 max 的任务：
当任务总数不超过 (n+1)×(max−1)+tot时，我们总能将其他任务插到空闲时间中去，不会引入额外的冻结时间（下左图）；而当任务数超过该值时，我们可以在将其横向添加每个 n+1 块的后面，同时不会引入额外的冻结时间（下右图）：
作者：宫水三叶https://leetcode.cn/problems/task-scheduler/description/
综上：
结果为 return Math.max(len, (n + 1) * (max - 1) + tot);
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int leastInterval (char [] tasks, int n) { int max = 0 ; int len = tasks.length; int [] hm = new int [26 ]; for (int i = 0 ; i < len; i++) { hm[tasks[i] - 'A' ]++; } for (int i = 0 ; i < 26 ; i++) { max = Math.max(hm[i], max); } int tot = 0 ; for (int i = 0 ; i < 26 ; i++) { if (hm[i] == max) tot++; } return Math.max(len, (n + 1 ) * (max - 1 ) + tot); } }
类区间调度的贪心题：
区间问题肯定按照区间的起点或者终点进行排序
labuladong-剪视频
将 clips 按照起点升序排序，起点相同的按照终点降序排序
然后比较所有起点小于 clips[0][1] 的区间，根据贪心策略，它们中终点最大的那个区间就是第二个会被选中的视频
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution { public int videoStitching (int [][] clips, int time) { Arrays.sort(clips, new Comparator <int []>(){ @Override public int compare (int [] clip1, int [] clip2) { if (clip1[0 ] == clip2[0 ]) { return clip2[1 ] - clip1[1 ]; } return clip1[0 ] - clip2[0 ]; } }); int i = 0 ; int curRight = 0 , rightMost = 0 ; int res = 0 ; while (i < clips.length && clips[i][0 ] <= curRight) { int [] clip = clips[i]; if (i == 0 ) { curRight = clip[1 ]; i++; res++; if (curRight >= time) return res; continue ; } while (i < clips.length && clips[i][0 ] <= curRight) { rightMost = Math.max(rightMost, clips[i][1 ]); i++; } res++; if (rightMost >= time) return res; curRight = rightMost; } return -1 ; } }
