想不到，根本想不到
买卖股票的最佳时机Ⅱ
leetcode：122. 买卖股票的最佳时机 II
贪心法
思路
任何一天的累计利润都可以拆成之前每天相比前一天的利润之和，因此最大利润就是收集了每天的正利润。
复杂度分析
时间复杂度：O(N)。
空间复杂度：O(1)。
注意点
略
代码实现
class Solution {
public:
// 任何一天的利润都可以表示为之前每天的利润之和
// 最大利润就收集每天的正利润
int maxProfit(vector<int>& prices) {
if(prices.size() == 1) return 0;
int profit = 0;
for(int i = 1;i < prices.size();i++){
int curProfit = prices[i] - prices[i - 1];
if(curProfit > 0) profit += curProfit;
}
return profit;
}
};
跳跃游戏
leetcode：55. 跳跃游戏
贪心法
思路
法一：
遍历覆盖范围的每个点，看最大覆盖范围是否包含最后下标
法二：
从后往前开始找0，因为之后通往终点全是正数，哪怕每次走1步，必能到。那么对于0前面的数，只要有一个满足（距离+1）的条件，这个0就可以被跳过。
复杂度分析
时间复杂度：O(N)。
空间复杂度：O(1)。
注意点
略。
代码实现
法一：
class Solution {
public:
// 遍历覆盖范围的每个点，看最大覆盖范围是否包含最后下标
bool canJump(vector<int>& nums) {
if(nums.size() == 1) return true;
int cover = 0;
for(int i = 0;i <= cover;i++){
cover = max(cover,nums[i] + i);
if(cover >= nums.size() - 1) return true;
}
return false;
}
};
法二：
class Solution {
public:
// 从后往前开始找0，因为之后通往终点全是正数，哪怕每次走1步，必能到。
// 那么对于0前面的数，只要有一个满足（距离+1）的条件，这个0就可以被跳过。
bool canJump(vector<int>& nums) {
int flag = -1;
for(int i = nums.size() - 2;i >= 0;i--){
// 如果flag为-1且当前数字为0，flag为当前下标（标记0的位置）
// 如果flag不为-1且当前下标(i)覆盖范围(i+nums[i])能跳过flag,flag重置为-1
if(flag == -1 && nums[i] == 0) flag = i;
if(flag != -1 && i + nums[i] > flag) flag = -1;
}
return flag == -1;
}
};
跳跃游戏Ⅱ
leetcode：45. 跳跃游戏 II
思路
遍历每个元素尝试更新下一轮最大范围（max(nextDist,i + nums[i])），走到本轮范围边界时，更新步数。
如果走到了末元素，跳出，返回。
复杂度分析
时间复杂度：O(N)。
空间复杂度：O(1)。
注意点
- 走到一轮边界才更新步数，而不是更新最大范围时更新。
代码实现
class Solution {
public:
int jump(vector<int>& nums) {
if(nums.size() == 1) return 0;
int curDist = 0;
int nextDist = 0;
int step = 0;
for(int i = 0;i < nums.size();i++){
nextDist = max(nextDist,i + nums[i]); // 每次尝试更新最大范围
if(i == curDist){ // 走到一轮范围边界时
curDist = nextDist; // 更新范围
step++; // 更新步数
if(curDist >= nums.size() - 1) break; // 如果走到末元素了，跳出，返回。
}
}
return step;
}
};