力扣top100(day04-06)--贪心算法
本文为力扣TOP100刷题笔记
笔者根据数据结构理论加上最近刷题整理了一套 数据结构理论加常用方法以下为该文章：
力扣外传之数据结构（一篇文章搞定数据结构）
121. 买卖股票的最佳时机
public class Solution {public int maxProfit(int prices[]) {int minprice = Integer.MAX_VALUE;int maxprofit = 0;for (int i = 0; i < prices.length; i++) {if (prices[i] < minprice) {minprice = prices[i];} else if (prices[i] - minprice > maxprofit) {maxprofit = prices[i] - minprice;}}return maxprofit;}
}算法思路
初始化：设置两个变量：
minprice：记录遍历过程中遇到的最低价格（初始为最大整数值）
maxprofit：记录当前能获得的最大利润（初始为0）遍历价格序列：
如果当前价格比
minprice低，更新最低价格否则，计算当前价格与最低价格的差值，如果大于
maxprofit则更新最大利润返回结果：最终返回
maxprofit关键点说明
一次遍历：算法只需要一次遍历即可完成，时间复杂度O(n)
空间效率：只使用了常数空间，空间复杂度O(1)
边界情况：
空数组或单元素数组直接返回0
价格持续下跌时利润保持为0
示例演示
假设输入
prices = [7,1,5,3,6,4]：
i=0: price=7
7 < MAX → minprice=7
i=1: price=1
1 < 7 → minprice=1
i=2: price=5
5-1=4 > 0 → maxprofit=4
i=3: price=3
3-1=2 < 4 → 无变化
i=4: price=6
6-1=5 > 4 → maxprofit=5
i=5: price=4
4-1=3 < 5 → 无变化
最终结果：5
复杂度分析
时间复杂度：O(n)，只需一次遍历
空间复杂度：O(1)，只使用了两个额外变量
优化说明
这个实现已经是该问题的最优解，因为：
必须检查每个价格才能确定最大利润
无法在比O(n)更好的时间复杂度内解决
空间使用已经是最小化
边界情况测试
空数组
[]→ 返回0单元素数组
[1]→ 返回0持续下跌
[7,6,4,3,1]→ 返回0持续上涨
[1,2,3,4,5]→ 返回4波动价格
[2,4,1,7]→ 返回6这个算法简洁高效地解决了股票买卖的最佳时机问题，是这类问题的经典解决方案。
55. 跳跃游戏
public class Solution {public boolean canJump(int[] nums) {int n = nums.length;int rightmost = 0; // 当前能到达的最远位置for (int i = 0; i < n; ++i) {// 只有当前位置可达时才处理if (i <= rightmost) {// 更新最远可达位置rightmost = Math.max(rightmost, i + nums[i]);// 如果已经可以到达终点if (rightmost >= n - 1) {return true;}}}return false;}
}关键点说明
rightmost变量：动态记录当前能跳到的最远位置
i <= rightmost判断：确保只处理可达位置
提前终止：一旦发现能到达终点立即返回
示例演示
假设输入
nums = [2,3,1,1,4]：
i=0:
0 <= 0 (true)
rightmost = max(0, 0+2) = 2
i=1:
1 <= 2 (true)
rightmost = max(2, 1+3) = 4
4 >= 4 → return true
复杂度分析
时间复杂度：O(n)，只需一次遍历
空间复杂度：O(1)，仅使用常数空间
边界情况测试
[0]→ true（起点即终点）
[0,2,3]→ false（卡在起点）
[1,0,1,0]→ false（无法跨越0）
[3,0,0,0]→ true（第一步就能跳到终点）算法正确性证明
通过维护可达的最远位置，可以确保：
不会遗漏任何可能的跳跃路径
贪心选择总是保持最优可达性
提前终止保证效率
这个实现是跳跃游戏问题的最优解，既高效又易于理解。