代码随想录算法训练营第三十二天| 122 买卖股票的最佳时机 || 55 跳跃游戏 45 跳跃游戏 ||

目录

122 买卖股票的最佳时机 ||

55 跳跃游戏

45 跳跃游戏 ||

---

122 买卖股票的最佳时机 ||

设置变量now代表此时买入的股票，为赋值为Integer.MAX_VALUE，遍历prices数组，有如下两种情况：

• 如果比now小说明不能售出，可以用当前price替换now，便于下次赚取更大的利益。
• 如果比now大说明可以售出，res加上二者的差值并且将now赋值为price。

class Solution {public int maxProfit(int[] prices) {int res = 0;int now = Integer.MAX_VALUE;for(int price : prices){if(now > price){now = price;}else{res += price - now;now = price;}}return res;}
}

时间复杂度O(n)

空间复杂度O(1)

55 跳跃游戏

设置变量range代表此时能调到的范围，初始值为0。

从0遍历到range，每次都判断此时nums[i] + i的值是否比当前range大，如果更大则进行更新。

判断range是否能到达最后一个下标，如果能就返回true，不能就继续遍历。

如果到达末尾后也不能到达则返回false。

class Solution {public boolean canJump(int[] nums) {int range = 0;for(int i = 0;i <= range;i++){range = Math.max(range,i + nums[i]);if(range >= nums.length - 1)return true;}return false;}
}

时间复杂度O(n)

空间复杂度O(1)

45 跳跃游戏 ||