Day28- 贪心算法part02

一、买卖股票的最佳时机II

题目一：122. 买卖股票的最佳时机II

122. 买卖股票的最佳时机 II

给你一个整数数组?prices?，其中?prices[i]?表示某支股票第?i?天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候?最多?只能持有?一股?股票。你也可以先购买，然后在?同一天?出售。

返回?你能获得的?最大?利润?。

贪心算法的核心思想是只要明天的价格比今天高，就在今天买入，明天卖出。这样，通过累积每一次的小利润，可以得到最大的总利润。

prices 数组表示股票每天的价格。函数 maxProfit 计算并返回最大利润,遍历价格数组，只要发现第二天的价格高于今天的价格，就计算这一天的利润，并累加到总利润中。最后返回总利润。

/*
 * @lc app=leetcode.cn id=122 lang=cpp
 *
 * [122] 买卖股票的最佳时机 II
 */

// @lc code=start
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        for (int i = 0; i < prices.size() - 1; ++i) {
            if (prices[i + 1] > prices[i]) {
                profit += prices[i + 1] - prices[i];
            }
        }
        return profit;
    }
};
// @lc code=end

二、跳跃游戏

题目一：55. 跳跃游戏

55. 跳跃游戏

给你一个非负整数数组?nums?，你最初位于数组的?第一个下标?。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回?true?；否则，返回?false?。

在每一步都更新能够到达的最远距离。遍历数组中的每个元素，不断更新从当前位置或之前的位置能够到达的最远距离。如果在任何时刻，这个最远距离小于当前位置的索引，这意味着无法到达当前位置，因此也就无法到达数组的最后一个位置。

/*
 * @lc app=leetcode.cn id=55 lang=cpp
 *
 * [55] 跳跃游戏
 */

// @lc code=start
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxReach = 0;  
        for (int i = 0; i < nums.size(); ++i) {
            if (i > maxReach) return false;
            maxReach = std::max(maxReach, i + nums[i]);
            if (maxReach >= nums.size() - 1) return true;
        }

        return false;  
    }
};
// @lc code=end

题目二：45. 跳跃游戏II

核心思想是在每一步跳跃中，都选择能够使跳得最远的选项。

在遍历数组的过程中，不断更新在当前跳跃范围内，能够达到的最远距离。一旦到达或超过当前跳跃范围的末尾，增加跳跃次数，并更新跳跃范围。

/*
 * @lc app=leetcode.cn id=45 lang=cpp
 *
 * [45] 跳跃游戏 II
 */

// @lc code=start
class Solution {
public:
    int jump(vector<int>& nums) {
        int jumps = 0, currentEnd = 0, farthest = 0;
    
        for (int i = 0; i < nums.size() - 1; ++i) {
            farthest = std::max(farthest, i + nums[i]);

            if (i == currentEnd) {
                jumps++;  
                currentEnd = farthest;  
                if (currentEnd >= nums.size() - 1) break;
            }
        }

        return jumps;
    }

};
// @lc code=end