Greedy Algorithm选编 代码随想录 贪心法原理 贪心的本质是选择每一阶段的局部最优，从而达到全局最优 。
这么说有点抽象，来举一个例子：
例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？
指定每次拿最大的，最终结果就是拿走最大数额的钱。
每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。
再举一个例子如果是 有一堆盒子，你有一个背包体积为n，如何把背包尽可能装满，如果还每次选最大的盒子，就不行了。这时候就需要动态规划。
法一：DP 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public boolean canJump (int [] nums) { int n=nums.length; boolean [] dp=new boolean [n]; dp[0 ]=true ; for (int i = 0 ; i < n-1 ; i++) { if (dp[i]){ for (int j = 1 ; j <= nums[i]; j++) { if (i+j>=n){ break ; } dp[i+j]=true ; } } } return dp[n-1 ]; }
法二：Greedy 贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点 。
1 2 3 4 5 6 7 8 9 10 public boolean canJump (int [] nums) { int cover=0 ; for (int i = 0 ; i <= cover; i++) { cover=Math.max(cover,i+nums[i]); if (cover>=nums.length-1 ){ return true ; } } return false ; }
You can assume that you can always reach the last index.
法一：DP 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 public class LeetCode45 { public int jump (int [] nums) { int n=nums.length; int [] dp=new int [n]; for (int i = 1 ; i <= nums[0 ]; i++) { if (i>=n){ break ; } dp[i]=1 ; } for (int i = 1 ; i < n-1 ; i++) { if (dp[i]>0 ){ for (int j = 1 ; j <= nums[i]; j++) { if (i+j>=n){ break ; } if (dp[i+j]==0 ){ dp[i+j]=dp[i]+1 ; }else { dp[i+j]=Math.min(dp[i+j],dp[i]+1 ); } } } } return dp[n-1 ]; } }
法二：Greedy 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int jump (int [] nums) { int result = 0 ; int end = 0 ; int temp = 0 ; for (int i = 0 ; i <= end && end < nums.length - 1 ; ++i) { temp = Math.max(temp, i + nums[i]); if (i == end) { end = temp; result++; } } return result; } }
Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
好题！
先从左向右，再从右向左
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public class LeetCode135 { public int candy (int [] ratings) { int n=ratings.length; int [] arr=new int [n]; Arrays.fill(arr,1 ); for (int i = 1 ; i < n; i++) { if (ratings[i]>ratings[i-1 ]){ arr[i]=arr[i-1 ]+1 ; } } for (int i = n-2 ; i >= 0 ; i--) { if (ratings[i]>ratings[i+1 ]){ arr[i]=Math.max(arr[i+1 ]+1 ,arr[i]); } } return Arrays.stream(arr).sum(); } }
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 public class LeetCode860 { public boolean lemonadeChange (int [] bills) { int five=0 ; int ten=0 ; for (int bill : bills) { if (bill==5 ){ five++; }else if (bill==10 ){ if (five==0 ){ return false ; } five--; ten++; }else { if (ten>=1 ){ ten--; }else if (five>=2 ){ five-=2 ; }else { return false ; } if (five>0 ){ five--; }else { return false ; } } } return true ; } }
那么本题的解题步骤为：
第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
第二步：从前向后遍历，遇到负数将其变为正数，同时K–
第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
第四步：求和
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public int largestSumAfterKNegations (int [] nums, int k) { nums = IntStream.of(nums) .boxed() .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1)) .mapToInt(Integer::intValue).toArray(); int n=nums.length; for (int i = 0 ; i < n; i++) { if (nums[i]<0 ){ nums[i]=-nums[i]; k--; if (k==0 ){ break ; } } } if ((k&1 )==1 ){ nums[n-1 ]=-nums[n-1 ]; } return Arrays.stream(nums).sum(); }
法一：暴力模拟 超时！
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public int canCompleteCircuit (int [] gas, int [] cost) { int n=gas.length; for (int i = 0 ; i < n; i++) { int rest=gas[i]-cost[i]; int index=(i+1 )%n; while (rest>=0 && index!=i){ rest+=gas[index]; rest-=cost[index]; index=(index+1 )%n; } if (rest>=0 && index==i){ return i; } } return -1 ; }
法二：Greedy
[^心路历程]: 有一个环形路上有n个站点； 每个站点都有一个好人或一个坏人； 好人会给你钱，坏人会收你一定的过路费，如果你带的钱不够付过路费，坏人会跳起来把你砍死； 问：从哪个站点出发，能绕一圈活着回到出发点?首先考虑一种情况：如果全部好人给你 的钱加起来 小于 坏人收的过路费之和，那么总有一次你的钱不够付过路费，你的结局注定会被砍死。假如你随机选一点 start 出发，那么你肯定会选一个有好人的站点开始，因为开始的时候你没有钱，遇到坏人只能被砍死；现在你在start出发，走到了某个站点end，被end站点的坏人砍死了，说明你在 [start, end) 存的钱不够付 end点坏人的过路费，因为start站点是个好人，所以在 (start, end) 里任何一点出发，你存的钱会比现在还少，还是会被end站点的坏人砍死；于是你重新读档，聪明的选择从 end+1点出发，继续你悲壮的征程； 终于有一天，你发现自己走到了尽头（下标是n-1)的站点而没有被砍死； 此时你犹豫了一下，那我继续往前走，身上的钱够不够你继续走到出发点Start?当然可以，因为开始已经判断过，好人给你的钱数是大于等于坏人要的过路费的，你现在攒的钱完全可以应付 [0, start) 这一段坏人向你收的过路费。(此处存疑) 这时候你的嘴角微微上扬，眼眶微微湿润，因为你已经知道这个世界的终极奥秘：Start就是这个问题的答案。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public int canCompleteCircuit (int [] gas, int [] cost) { int n=gas.length; int cur=0 ; int total=0 ; int start=0 ; for (int i = 0 ; i < n; i++) { cur+=gas[i]-cost[i]; total+=gas[i]-cost[i]; if (cur<0 ){ start=i+1 ; cur=0 ; } } if (total<0 ){ return -1 ; } return start; }
Greedy解法 局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值 。
整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列 。
局部最优推出全局最优，并举不出反例，那么试试贪心！
（为方便表述，以下说的峰值都是指局部峰值）
实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）
这就是贪心所贪的地方，让峰值尽可能的保持峰值，然后删除单一坡度上的节点 。
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 wiggleMaxLength (int [] nums) { if (nums.length <= 1 ) { return nums.length; } int curDiff = 0 ; int preDiff = 0 ; int count = 1 ; for (int i = 1 ; i < nums.length; i++) { curDiff = nums[i] - nums[i - 1 ]; if ((curDiff > 0 && preDiff <= 0 ) || (curDiff < 0 && preDiff >= 0 )) { count++; preDiff = curDiff; } } return count; } }
时间复杂度：$O(n)$
空间复杂度：$O(1)$
Dynamic Programming基础版 考虑用动态规划的思想来解决这个问题。
很容易可以发现，对于我们当前考虑的这个数，要么是作为山峰（即nums[i] > nums[i-1]），要么是作为山谷（即nums[i] < nums[i - 1]）。
设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]接到前面某个山峰后面，作为山谷。
初始状态：
由于一个数可以接到前面的某个数后面，也可以以自身为子序列的起点，所以初始状态为：dp[0][0] = dp[0][1] = 1。
时间复杂度：$O(n^2)$
空间复杂度：$O(n)$
Dynamic Programming进阶版 可以用两棵线段树来维护区间的最大值
每次更新dp[i][0]，则在tree1的nums[i]位置值更新为dp[i][0]
每次更新dp[i][1]，则在tree2的nums[i]位置值更新为dp[i][1]
则dp转移方程中就没有必要j从0遍历到i-1，可以直接在线段树中查询指定区间的值即可。
时间复杂度：$O(n\log n)$
空间复杂度：$O(n)$
Greedy解法 局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
全局最优：选取最大“连续和”
局部最优的情况下，并记录最大的“连续和”，可以推出全局最优 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public int maxSubArray (int [] nums) { int n=nums.length; int max=Integer.MIN_VALUE; int count=0 ; for (int i = 0 ; i < n; i++) { count+=nums[i]; if (count>max){ max=count; } if (count<0 ){ count=0 ; } } return max; }
DP解法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int maxSubArray (int [] nums) { int n=nums.length; int [] dp=new int [n]; dp[0 ]=nums[0 ]; int max=dp[0 ]; for (int i=1 ; i<n; i++){ if (dp[i-1 ]>0 ){ dp[i]=dp[i-1 ]+nums[i]; }else { dp[i]=nums[i]; } max=Math.max(max,dp[i]); } return max; } }
labuladong 什么是贪心算法呢？贪心算法可以认为是动态规划算法的一个特例，相比动态规划，使用贪心算法需要满足更多的条件（贪心选择性质），但是效率比动态规划要高。
比如说一个算法问题使用暴力解法需要指数级时间，如果能使用动态规划消除重叠子问题，就可以降到多项式级别的时间，如果满足贪心选择性质，那么可以进一步降低时间复杂度，达到线性级别的。
什么是贪心选择性质呢，简单说就是：每一步都做出一个局部最优的选择，最终的结果就是全局最优。注意哦，这是一种特殊性质，其实只有一部分问题拥有这个性质。
比如你面前放着 100 张人民币，你只能拿十张，怎么才能拿最多的面额？显然每次选择剩下钞票中面值最大的一张，最后你的选择一定是最优的。
然而，大部分问题明显不具有贪心选择性质。比如打斗地主，对手出对儿三，按照贪心策略，你应该出尽可能小的牌刚好压制住对方，但现实情况我们甚至可能会出王炸。这种情况就不能用贪心算法，而得使用动态规划解决。
区间调度问题 Interval Scheduling
最多有几个不冲突的区间？
正确的思路其实很简单，可以分为以下三步：
从区间集合 intvs 中选择一个区间 x，这个 x 是在当前所有区间中结束最早的 （end 最小）。
把所有与 x 区间相交的区间从区间集合 intvs 中删除。
重复步骤 1 和 2，直到 intvs 为空为止。之前选出的那些 x 就是最大不相交子集。
make the rest of the intervals non-overlapping
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public class LeetCode435 { public int eraseOverlapIntervals (int [][] intervals) { int n=intervals.length; Arrays.sort(intervals, new Comparator <int []>() { @Override public int compare (int [] o1, int [] o2) { return o1[1 ]-o2[1 ]; } }); int count=1 ; int end=intervals[0 ][1 ]; for (int [] interval : intervals) { int start=interval[0 ]; if (start>=end){ count++; end=interval[1 ]; } } return n-count; } }
注意：
1 2 3 4 5 6 7 8 9 10 11 12 Arrays.sort(intvs, new Comparator <int []>() { public int compare (int [] a, int [] b) { return a[1 ] - b[1 ]; } }); Arrays.sort(points, (o1,o2)->{ if (o1[1 ]>o2[1 ]) return 1 ; if (o1[1 ]<o2[1 ]) return -1 ; return 0 ; });
依然是求最大不重叠区间数
每个不重叠区间都需要一个箭，每多一个不重叠区间，就多需要一根箭
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 public class LeetCode452 { public int findMinArrowShots (int [][] points) { Arrays.sort(points, new Comparator <int []>() { @Override public int compare (int [] o1, int [] o2) { if (o1[1 ]>o2[1 ]){ return 1 ; } if (o1[1 ]<o2[1 ]){ return -1 ; } return 0 ; } }); int count=1 ; int end=points[0 ][1 ]; for (int [] point : points) { int start=point[0 ]; if (start>end){ count++; end=point[1 ]; } } return count; } }
自选 605. Can Place Flowers 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public boolean canPlaceFlowers (int [] flowerbed, int n) { if (n==0 ){ return true ; } int len=flowerbed.length; int count=0 ; for (int i = 0 ; i < len; i++) { if (flowerbed[i]==1 ){ continue ; } boolean leftPlanted=i>0 && flowerbed[i-1 ]==1 ; boolean rightPlanted=i<len-1 && flowerbed[i+1 ]==1 ; if (!leftPlanted && !rightPlanted){ flowerbed[i]=1 ; count++; if (count>=n){ return true ; } } } return false ; }
2340. Minimum Adjacent Swaps to Make a Valid Array 1 2 3 4 5 6 7 8 9 10 11 12 13 14 public int minimumSwaps (int [] nums) { int n=nums.length; int min=0 ; int max=n-1 ; for (int i = 1 ; i < n; i++) { if (nums[i]<nums[min]){ min=i; } if (nums[n-1 -i]>nums[max]){ max=n-1 -i; } } return min-0 +n-1 -max-(min>max ? 1 : 0 ); }
280. Wiggle Sort 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public void wiggleSort (int [] nums) { int n=nums.length; if (n==1 ){ return ; } for (int i = 0 ; i < n-1 ; i++) { if (i%2 ==0 && nums[i]>nums[i+1 ] || i%2 ==1 && nums[i]<nums[i+1 ]){ swap(nums,i,i+1 ); } } } void swap (int [] arr, int i, int j) { int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; }
1564. Put Boxes Into the Warehouse I 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public int maxBoxesInWarehouse (int [] boxes, int [] warehouse) { Arrays.sort(boxes); Deque<Integer> stack=new LinkedList <>(); stack.push(warehouse[0 ]); for (int i = 1 ; i < warehouse.length; i++) { stack.push(Math.min(warehouse[i],stack.peek())); } int res=0 ; for (int box : boxes) { if (stack.isEmpty()){ break ; } while (!stack.isEmpty() && stack.peek()<box){ stack.pop(); } if (!stack.isEmpty()){ res++; stack.pop(); } } return res; }
自己想的还不够贪！
思路：
the edge is the largest space we can offer
if this box can’t fit at the edge, it can fit nowhere
try to fit from the largest box
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public int maxBoxesInWarehouse (int [] boxes, int [] warehouse) { int res=0 ; int idx=0 ; Arrays.sort(boxes); for (int i=boxes.length-1 ; i>=0 ; i--){ if (idx==warehouse.length){ break ; } if (boxes[i]<=warehouse[idx]){ res++; idx++; } } return res; }
1580. Put Boxes Into the Warehouse II 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public int maxBoxesInWarehouse (int [] boxes, int [] warehouse) { int res=0 ; Arrays.sort(boxes); int p1=0 ; int p2=warehouse.length-1 ; for (int i = boxes.length - 1 ; i >= 0 && p1<=p2; i--) { if (boxes[i]<=warehouse[p1]){ res++; p1++; }else if (boxes[i]<=warehouse[p2]){ res++; p2--; } } return res; }
2439. Minimize Maximum of Array 1 2 3 4 5 6 7 8 9 10 public int minimizeArrayValue (int [] nums) { int n=nums.length; long ans=0 ; long sum=0 ; for (int i = 0 ; i < n; i++) { sum+=nums[i]; ans=Math.max(ans,(sum+i)/(i+1 )); } return (int )ans; }