hot100贪心专题
1 买卖股票的最佳时机
res用于保存可能获得的最大利润，minPrice用于保存在遍历过程中的最小入手价格，初始化为Integer.MAX_VALUE;
遍历prices数组，更新minPrice和res。
最后返回res即可。
因为本题只能买入一次
class Solution { public int maxProfit(int[] prices) { int len = prices.length; int res = 0, minPrice = Integer.MAX_VALUE; for (int i = 0; i < len; i++) { if (prices[i] < minPrice) { minPrice = prices[i]; } res = Math.max(res, prices[i] - minPrice); } return res; } }2 跳跃游戏
先单独处理一个元素的情况
maxReach = 0
for循环的条件要写 i < nums.length && i <= maxReach，只遍历「可达的位置」，且不越界。
循环里面动态更新maxReach
最后只需要判断i >= maxReach即可。
class Solution { public boolean canJump(int[] nums) { // 处理特殊情况：数组长度为1，直接返回true（已经在终点） if (nums.length == 1) { return true; } int maxReach = 0; // 初始能到达的最远位置（从索引0开始） // 循环条件：i不超过当前能到达的最远位置，且不越界 for (int i = 0; i < nums.length && i <= maxReach; i++) { // 更新能到达的最远位置 maxReach = Math.max(maxReach, i + nums[i]); // 提前终止：如果已经能到达最后一个位置，直接返回true if (maxReach >= nums.length - 1) { return true; } } // 循环结束仍未到达最后一个位置，返回false return false; } }3 跳跃游戏Ⅱ
贪心策略：每一次跳跃都选择 “能跳的最远位置” 作为下一步的边界，这样能保证每一步都是最优的，最终得到全局最少次数。
res用于存跳的步数。
currentEnd用于存当前能到的最远边界，初始化为0；
maxReach是全局能到的最远边界，初始化为0；
class Solution { public int jump(int[] nums) { // 特殊情况：数组长度为1，不需要跳跃 if (nums.length == 1) { return 0; } int steps = 0; // 最少跳跃次数 int end = 0; // 当前步能到达的最远边界 int maxReach = 0; // 全局能到达的最远位置 // 遍历数组（注意：不用遍历最后一个元素，因为到了就不用跳了） for (int i = 0; i < nums.length - 1; i++) { // 更新全局最远可达位置 maxReach = Math.max(maxReach, i + nums[i]); // 当遍历到当前步的边界时，需要跳一次 if (i == end) { steps++; // 跳跃次数+1 end = maxReach; // 更新下一步的边界 // 提前终止：如果下一步边界已到终点，不用继续遍历 if (end >= nums.length - 1) { break; } } } return steps; } }4.划分字母区间
预处理：先记录每个字母在字符串中出现的「最后位置」（maxIndex 数组）；
遍历划分：遍历字符串时，维护当前片段的「最远结束位置（curMax）」，当遍历到这个最远位置时，说明当前片段可以闭合，记录长度并开启新片段。
class Solution { public List<Integer> partitionLabels(String s) { // 1. 初始化结果列表，存储每个片段的长度 List<Integer> res = new ArrayList<>(); // 2. 定义maxIndex数组（长度26对应26个小写字母），记录每个字母最后出现的索引 int[] maxIndex = new int[26]; // 3. 把字符串转为字符数组，方便遍历 char[] sArr = s.toCharArray(); // 4. 预处理：遍历字符串，记录每个字母的最后出现位置 for (int i = 0; i < sArr.length; i++) { // 字符转数组索引：比如 'a'->0，'b'->1... maxIndex[sArr[i] - 'a'] = i; } // 5. 定义两个关键变量： // start：当前片段的起始索引（初始为0） // curMax：当前片段需要覆盖的最远索引（初始为0） int start = 0; int curMax = 0; // 6. 遍历字符串，划分片段 for (int i = 0; i < sArr.length; i++) { // 6.1 更新当前片段的最远结束位置（必须包含当前字母的最后出现位置） curMax = Math.max(maxIndex[sArr[i] - 'a'], curMax); // 6.2 当遍历到当前片段的最远结束位置时，闭合当前片段 if (i == curMax) { // 计算当前片段长度（i - start + 1），加入结果 res.add(i - start + 1); // 开启新片段：起始位置为当前索引+1 start = i + 1; } } // 7. 返回结果列表 return res; } }