代码随想录算法训练营 Day24 | 贪心算法 part02

122. 买卖股票的最佳时机 II给你一个整数数组prices其中prices[i]表示某支股票第i天的价格。在每一天你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。然而你可以在 同一天 多次买卖该股票但要确保你持有的股票不超过一股。返回你能获得的 最大 利润。class Solution { public: int maxProfit(vectorint prices) { int ans 0; // 从第二天开始遍历与前一天比较 for (int i 1; i prices.size(); i) { // 计算今天的股价减去昨天的股价今天的收益 int tmp prices[i] - prices[i - 1]; // 核心贪心逻辑 // 只要今天比昨天涨了差价 0我就把这个利润收入囊中。 // 如果跌了差价 0我就假装没看见不操作。 if (tmp 0) ans tmp; } return ans; } };总结1. 拆解收益假设股票价格变化是[1, 2, 3, 4, 5]持有不动第一天买最后一天卖。利润 5−14。贪心算法第1天买第2天卖赚 2−112−11第2天买第3天卖赚 3−213−21第3天买第4天卖赚 4−314−31第4天买第5天卖赚 5−415−41总利润11114。结论连续上涨的区间分次买卖和一次买卖的收益是完全等价的。(B−A)(B−C)(C−A)所以我们不需要去寻找复杂的“波峰波谷”只需要把每一天比昨天涨了的钱加起来即可。2. 处理下跌假设价格变化是[5, 4, 3, 2, 1]每天都在跌tmp都是负数。if (tmp 0)不成立。ans保持为 0。结果正确亏钱的买卖我们不做。3. 复杂情况假设价格变化是[1, 5, 3, 6]1 - 5涨 4加上。贪心策略赚了就跑5 - 3跌 2忽略。贪心策略亏了不卖或者止损3 - 6涨 3加上。总收益437。这正是“第一天买入第二天卖出第三天买入第四天卖出”的真实最大收益。55. 跳跃游戏给你一个非负整数数组nums你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标如果可以返回true否则返回false。class Solution { public: bool canJump(vectorint nums) { int right 0; // 定义当前能跳到的最远右边界闭区间 // 遍历数组注意循环条件的精妙之处i right // 意思是只有 i 在当前能到达的范围内循环才继续 // 如果 i 超过了 right说明断了跳不过去了循环自动终止 for (int i 0; i right; i) { // 贪心策略在当前可达范围内不断更新能跳到的最远距离 // 站在位置 i最远能跳到 i nums[i] // right 取之前的最大值和当前计算值的较大者 right max(right, i nums[i]); // 如果最远距离已经超过了或等于最后一个位置的下标 // 说明终点可达直接返回 true if (right nums.size() - 1) return true; } // 如果循环结束即 i 走到了 right1 还没到达终点 // 说明中间断了无法继续前行 return false; } };总结思路不去管“我是从哪跳过来的”只管“我最远能跳到哪”。核心逻辑初始时你站在位置 0最远能跳到right 0。你在[0, right]这个范围内移动每走到一个位置i就看看能不能把right推得更远。一旦right扩大到了终点就赢了。如果你在[0, right]走完了right却没变大且没到终点说明被困住了跳不出去。复杂度O(N)只需要一次遍历。45. 跳跃游戏 II给定一个长度为n的 0 索引整数数组nums。初始位置在下标 0。每个元素nums[i]表示从索引i向后跳转的最大长度。换句话说如果你在索引i处你可以跳转到任意(i j)处0 j nums[i]且i j n返回到达n - 1的最小跳跃次数。测试用例保证可以到达n - 1。class Solution { public: int jump(vectorint nums) { int cur 0; // 当前这一步能跳到的右边界当前覆盖范围 int cover 0; // 下一步能跳到的最远右边界下一跳的最大覆盖范围 int ans 0; // 跳跃次数 // 注意循环条件i nums.size() - 1 // 因为我们是站在位置 i 向后看如果已经到了最后一个位置就不需要再跳了 for (int i 0; i nums.size() - 1; i) { // 在当前覆盖范围内不断更新下一步能跳到的最远距离 // 贪心策略寻找下一跳的最优落点 cover max(cover, i nums[i]); // 当 i 走到了当前覆盖范围的边界 cur // 说明当前的“步数”已经用完了必须进行下一次跳跃 if (i cur) { ans; // 增加跳跃次数 cur cover; // 更新当前覆盖范围为之前计算好的最远距离 // 优化点可选如果新的范围已经覆盖了终点可以直接 break // if (cur nums.size() - 1) break; } } return ans; } };总结这道题的贪心逻辑稍微有点绕难点在于理解cur和cover的关系。我们可以将其想象成 “加油站” 的过程cur当前油量代表你当前这一跳能走到的最远边界。cover潜在最大油量代表你在走到cur边界的路上沿途搜集到的所有“加油卡”这些卡能让你下一跳跳得更远。假设nums [2, 3, 1, 1, 4]初始状态ans 0cur 0(站在起点)cover 0i 0:cover max(0, 02) 2。 (在起点最远能跳到下标 2)i cur(0 0)走到了当前边界必须跳跃了第一跳ans 1cur 2。 (现在我有权走到下标 2)i 1:cover max(2, 13) 4。 (在下标 1 处发现能跳到 4更新最远距离)i ! cur还在当前这一跳的范围内继续走。i 2:cover max(4, 21) 4。i cur(2 2)走到了当前边界下标 2用尽了当前步数必须再跳一次第二跳ans 2cur 4。 (更新边界为 4)循环结束i循环到size-2即止。此时cur 4已经覆盖了终点。返回ans 2。为什么是i nums.size() - 1这是一个非常关键的边界处理。如果条件写成i nums.size()当i到达终点时如果i cur代码会再执行一次ans。但实际上当你已经到达终点时不需要再跳跃了。写成i nums.size() - 1意味着我们只考虑在终点之前的位置起跳。只要我们在倒数第二个位置时计算出的cover能覆盖终点循环结束时ans就是正确的步数。1005. K 次取反后最大化的数组和给你一个整数数组nums和一个整数k按以下方法修改该数组选择某个下标i并将nums[i]替换为-nums[i]。重复这个过程恰好k次。可以多次选择同一个下标i。以这种方式修改数组后返回数组 可能的最大和 。class Solution { public: // 自定义排序规则按绝对值从小到大排序 static bool cmp(int a, int b) { return abs(a) abs(b); } int largestSumAfterKNegations(vectorint nums, int k) { int sum 0; // 第一步排序 // 将数组按照绝对值从小到大排列。 // 排序后大的负数如 -5会排在后面小的正数如 1会排在前面。 sort(nums.begin(), nums.end(), cmp); // 第二步优先处理负数贪心策略 // 从后往前遍历先处理绝对值大的 for (int i nums.size() - 1; i 0; i--) { // 如果还有翻转次数且当前是负数 if (k 0 nums[i] 0) { nums[i] -nums[i]; // 翻转成整数 k--; // 消耗一次次数 } } // 第三步处理剩余的次数 // 此时数组中可能全为正数或者 k 还有剩余。 // 无论 k 剩多少我们只需要对绝对值最小的元素也就是排序后的 nums[0]操作。 // 因为翻转两次等于没变所以只看 k 是奇数还是偶数。 int t k % 2; if (t) { nums[0] -nums[0]; // 如果是奇数翻转一次最小的元素损失最小 } // 第四步求和 for (int i 0; i nums.size(); i) sum nums[i]; return sum; } };总结1. 第一阶段收益最大化目标通过翻转让总和增加得最多。策略翻转绝对值最大的负数。例如-5翻转成5总和增加了10。例如-1翻转成1总和只增加了2。代码体现sort将绝对值大的负数排在后面循环从后往前优先处理大负数。2. 第二阶段损失最小化场景如果负数都翻完了k还有剩余。策略反复翻转绝对值最小的数。如果是偶数次翻转相当于没变-a - a - -a - a。如果是奇数次翻转相当于翻转一次。为了让总和减少得最少我们必须选择绝对值最小的那个数下手。代码体现int t k % 2;这一步非常关键利用数学性质将 O(K)的操作降为 O(1)。nums[0]因为是按绝对值排序的所以它永远是当前绝对值最小的数。3. 为什么按绝对值排序这是这道题最巧妙的地方。如果我们按普通的大小排序从小到大负数会在前面正数在后面。处理完负数后我们要找最小正数如果有剩余次数就需要跨过中间的数。按绝对值排序的好处是大负数如-8会沉到后面容易被优先遍历到。小正数如1会浮到前面容易作为最后的“牺牲品”。这样nums[0]永远是那个“如果要受损就让它受损最小”的元素。4. 复杂度分析时间复杂度O(Nlog⁡N)主要是排序的时间复杂度。空间复杂度O(1)除了排序使用的栈空间外没有使用额外空间。