贪心算法2
目录
【贪心算法2】
力扣122.买卖股票最佳时机Ⅱ
链接:
思路
要求最大利润，可以分解成子问题求解，在最低价格买入，最高价格卖出。
假如第0天价格最低，第3天价格最高，利润=prices[3] - pricnes[0],
可以将利润公式拆解成
(prices[3]-prices[2])+(prices[2]-prices[1])+(prices[1]-prices[0])
最终变成了求相邻两天的利润，所以可以得到一个关于利润的列表，只需要将这个列表大于0的相加即可求出最大利润
方法1:
class Solution {
public int maxProfit(int[] prices) {
int res = 0;
for(int i = 1;i<prices.length;i++){
res += Math.max(prices[i] - prices[i-1],0);
}
return res;
}
}相似题型
思路
上一道题是求利润最大化，而这道题是只能进行一次买卖，要求这一次利润最大
121.买卖股票的最佳时机
链接:
class Solution {
public int maxProfit(int[] prices) {
int res = 0;
int minPrice = prices[0];
for (int p : prices) {
res = Math.max(res, p - minPrice);
minPrice = Math.min(minPrice, p);
}
return res;
}
}55.跳跃游戏
链接:
class Solution {
public boolean canJump(int[] nums) {
if(nums.length == 1) return true;
int cover = 0;
for(int i =0;i<=cover;i++){
cover = Math.max(i + nums[i],cover);
if(cover >= nums.length - 1){
return true;
}
}
return false;
}
}45.跳跃游戏Ⅱ
思路
这道题需要记录2个距离，一个是当前位置能走的最大距离和下一步能走的最大距离，当下一步能走的最大距离覆盖终点即为最优解。注意要先更新下一步最大距离，当i=当前最大距离时再更新当前最大距离。
链接:
class Solution {
public int jump(int[] nums) {
if (nums.length == 1)
return 0;
int cover_1 = 0; // 当前位置的覆盖范围
int cover_2 = 0; // 下一个位置的覆盖范围
int cnt = 0; // 记录跳次数
for (int i = 0; i < nums.length; i++) {
cover_2 = Math.max(i + nums[i], cover_2);
// 此时只需要走一步即可到达终点
if (cover_2 >= nums.length - 1) {
cnt++;
break;
}
// 走到当前覆盖的最大区域时，更新下一步可达的最大区域
if (i == cover_1) {
cover_1 = cover_2;
cnt++;
}
}
return cnt;
}
}