LeetCode Hot 100 题解 · 贪心算法专题本专题收录 LeetCode Hot 100 中所有 贪心算法专题 相关题目。每道题提供最直接、最容易理解的解题思路包含详细注释的代码实现方便笔试和面试复习。 目录题号题目难度核心思路121121.买卖股票的最佳时机简单只能买卖一次那么我就可以枚举每一天作为我卖出去的日子这样想的话那我每天只需要看前些天最低多少钱可以买下这只股票这个差值就是我这一天卖能得到的最大值。利用一个全局变量迭代更新一下每天的最大值即可。5555.跳跃游戏中等这个题是看我们能不能到达终点只需要在每次我们到达某个位置之前判断是否可以到达这个位置。如果可以更新下一次可以到达的最远位置如果不可以直接return false。当循环走完的时候就说明我们能到达终点4545.跳跃游戏II 困难相比于55.跳跃游戏 本题需要返回的是到达终点的最小跳跃次数那当然的思路就是能不跳跃就不跳跃比如能1-3就不1-2-3到达某个位置i之前更新i1到inums[i] in的最小跳跃次数即dp[j]Math.min(dp[j],dp[i]1);763763.划分字母区间I 困难这个题是要求对字符串进行分割要求同一字母必须划分在同一区间且划分区间数最多。那我们想的就是能划分就划分能划分才划分。那其实我们需要在每次看到位置i的时候能够预知字符串中s[i]的最远位置last[s[i]]这样我们就可以拿到当前划分的区间的关于s[i]的最右距离right在每次到达一个位置i之后更新right Math.max(right,last[s[i]]);如果当前iright证明这个区间已经拿到了将左边界left更新为i1如果i!right说明当前区间还没走完121.买卖股票的最佳时机题目链接121.买卖股票的最佳时机题目描述给你一个数组每个元素表示达到当前位置可以跳跃的最远距离一开始你在位置0问你不限制跳跃次数的话你能调到终点n-1吗思路一贪心枚举每一天作为卖票的日子记录更新买票的最低价格核心思想只能买卖一次那么我就可以枚举每一天作为我卖出去的日子这样想的话那我每天只需要看前些天最低多少钱可以买下这只股票这个差值就是我这一天卖能得到的最大值。利用一个全局变量迭代更新一下每天的最大值即可。时间复杂度O ( n ) O(n)O(n)其中 n 为给定天数数组的长度。空间复杂度O ( 1 ) O(1)O(1)。classSolution{publicintmaxProfit(int[]prices){// 很直观的贪心枚举每个值作为卖出点那么要减去之前最小的intans0;intpreInteger.MAX_VALUE;// pre表示当前卖出之前这些天股票最低的价格for(intp:prices){intcurp-pre;// 当天卖出的最大价格今天的价格-之前最低的价格ansMath.max(ans,cur);// 维护结果preMath.min(pre,p);// 维护当天前的最低价格}returnans;}}55.跳跃游戏题目链接 55.跳跃游戏题目描述给你一个数组每个元素表示当前股票的价格问你如果只能对这只股票买卖一次最多可以获得多少钱。思路一贪心枚举每个位置记录更新其可以到达的最右位置核心思想只能买卖一次那么我就可以枚举每一天作为我卖出去的日子这样想的话那我每天只需要看前些天最低多少钱可以买下这只股票这个差值就是我这一天卖能得到的最大值。利用一个全局变量迭代更新一下每天的最大值即可。时间复杂度O ( n ) O(n)O(n)其中 n 为 给定位置数组的长度。空间复杂度O ( 1 ) O(1)O(1)。classSolution{publicbooleancanJump(int[]nums){intnnums.length;intr_max0;// r_max表示到达当前位置前可以到达的最右距离【循环不变量】for(inti0;in;i){if(r_maxi)returnfalse;r_maxMath.max(r_max,inums[i]);}// 能走到这里说明每一个i都可达in-1必然可达终点就是n-1returntrue;}}45.跳跃游戏II题目链接45.跳跃游戏II题目描述给你一个数组每个元素表示当前股票的价格问你如果只能对这只股票买卖一次最多可以获得多少钱。思路一贪心到达某个位置后更新他可以到达的所有位置的最小跳跃次数核心思想相比于55.跳跃游戏 本题需要返回的是到达终点的最小跳跃次数那当然的思路就是能不跳跃就不跳跃比如能1-3就不1-2-3到达某个位置i之前更新i1到inums[i] in的最小跳跃次数, 即dp[j]Math.min(dp[j],dp[i]1);时间复杂度O ( n ) O(n)O(n)其中 n 为 给定位置数组的长度。空间复杂度O ( n ) O(n)O(n)其中 n 为 给定位置数组的长度需要开dp数组。classSolution{publicintjump(int[]nums){intnnums.length;intdp[]newint[n];// dp[i]存储到达i位置的最小跳跃次数Arrays.fill(dp,Integer.MAX_VALUE);// dp为min语义时候的常见初始化方式dp[0]0;// 一开始就在位置0for(inti0;in;i){// 在到达位置i后更新其能到达的所有位置的最小跳跃次数for(intji1;jinums[i]jn;j){dp[j]Math.min(dp[j],dp[i]1);}}returndp[n-1];}}763.划分字母区间题目链接763.划分字母区间题目描述给你一个字符串要求你把这个字符串进行划分同一个字符必须划分为一组要求划分的区间数最多。思路一贪心【维护当前划分区间的右边界】核心思想这个题是要求对字符串进行分割要求同一字母必须划分在同一区间且划分区间数最多。那我们想的就是能划分就划分能划分才划分。那其实我们需要在每次看到位置i的时候能够预知字符串中s[i]的最远位置last[s[i]]这样我们就可以拿到当前划分的区间的关于s[i]的最右距离right在每次到达一个位置i之后更新right Math.max(right,last[s[i]]);a.如果当前iright证明这个区间已经拿到了将左边界left更新为i1b. 如果i!right说明当前区间还没走完时间复杂度O ( n ) O(n)O(n)其中 n 为 给定字符串的长度。空间复杂度O ( n ) O(n)O(n)其中 n 为 给定字符串的长度因为需要每个出现过的字符的最远位置classSolution{publicListIntegerpartitionLabels(Strings){ListIntegeransnewArrayList();// 存储结果划分区间的长度数组char[]chss.toCharArray();int[]lastnewint[128];// last[i]存储当前字符的最远位置for(inti0;ichs.length;i){last[chs[i]]i;}intleft0,rightInteger.MIN_VALUE;// [left,right]表示当前划分区间for(inti0;is.length();i){rightMath.max(right,last[chs[i]]);// 更新当前区间的右边界if(iright){ans.add(right-left1);lefti1;}}returnans;}}
