LeetCode Hot 100 题解 · 贪心算法专题-北京尧图网络

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;}}

LeetCode Hot 100 题解 · 贪心算法专题

相关推荐

DreamFly：基于因果记忆与扩散模型的无人机视觉语言导航技术解析

虚拟机与主机文件传输全攻略：共享文件夹、SCP、SMB与HTTP方案详解

达索系统工业软件全解析：从CAD到数字孪生的完整生态

更多资讯

个人智能体（Personal Agent）火爆背后：从“交互工具”到“代行中介”，重塑决策链的商业新博弈

基于FCN的腹部CT脊椎分割实战：从数据预处理到推理后处理

KNN实战ChineseMnist：15000张中文手写字的识别与调优

《雷达原理》全套PPT课件（西安交通大学）

C# ASP.NET通讯录系统开发实战：从数据表设计到避坑指南

一文看懂 9 大 AI 模型：原理、落地与适用企业

今日更新

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？