算法奇妙屋(三十五)-贪心算法学习之路 2

文章目录一. 力扣 [376. 摆动序列](https://leetcode.cn/problems/wiggle-subsequence/description/)1. 题目解析2. 算法原理3. 代码二. 力扣 [300. 最长递增子序列](https://leetcode.cn/problems/longest-increasing-subsequence/description/)1. 题目解析2. 算法原理3. 代码三. 力扣 [334. 递增的三元子序列](https://leetcode.cn/problems/increasing-triplet-subsequence/description/)1. 题目解析2. 算法原理3. 代码四. 力扣 [674. 最长连续递增序列](https://leetcode.cn/problems/longest-continuous-increasing-subsequence/description/)1. 题目解析2. 算法原理3. 代码一. 力扣376. 摆动序列1. 题目解析题目这里看一眼图片就能理解2. 算法原理看下面图解, 最后一个值不会被计算上, 所有将ret初始值赋值为13. 代码classSolution{publicintwiggleMaxLength(int[]nums){intleft0;intret1;for(inti0;inums.length-1;i){intrightnums[i1]-nums[i];if(right0){continue;}if(left*right0){ret;leftright;}}returnret;}}二. 力扣300. 最长递增子序列1. 题目解析在算法奇妙屋(十九)-子序列问题(动态规划)这篇博客中我们使用动态规划解决过这道题, 这里不过多赘述题目2. 算法原理贪心算法需要动态规划和二分查找的铺垫, 这里我们是根据示例, 下标从头到尾一步步模拟的, 制作不易~回忆动态规划贪心算法主体3. 代码classSolution{publicintlengthOfLIS(int[]nums){inttail1;intnnums.length;int[]dpnewint[n];dp[0]nums[0];for(inti1;in;i){if(nums[i]dp[tail-1]){dp[tail]nums[i];continue;}intleft0;intrighttail-1;while(leftright){intmidleft(right-left)/2;if(dp[mid]nums[i]){leftmid1;}else{rightmid;}}if(nums[i]dp[left]){dp[left]nums[i];}}returntail;}}三. 力扣334. 递增的三元子序列1. 题目解析这道题和上道题(最长递增子序列)十分相似, 就只多了个条件, 长度为3时, 返回true2. 算法原理这里和上道题的算法原理基本一致, 这里直接copy3. 代码classSolution{publicbooleanincreasingTriplet(int[]nums){intnnums.length;if(n3){returnfalse;}int[]dpnewint[3];inttail1;dp[0]nums[0];for(inti1;in;i){intleft0;intrighttail-1;if(dp[tail-1]nums[i]){dp[tail]nums[i];}else{while(leftright){intmid(leftright)/2;if(dp[mid]nums[i]){leftmid1;}else{rightmid;}}}if(tail3){returntrue;}if(nums[i]dp[left]){dp[left]nums[i];}}returnfalse;}}四. 力扣674. 最长连续递增序列1. 题目解析最长递增子序列的更简单版本, 这里是子数组2. 算法原理3. 代码classSolution{publicintfindLengthOfLCIS(int[]nums){intret0;intnnums.length;for(inti0;in;){intji1;while(jnnums[j]nums[j-1]){j;}retMath.max(ret,j-i);ij;}returnret;}}