美丽乡村建设网站模板网站建设网站推广服务公司

美丽乡村建设网站模板,网站建设网站推广服务公司,网站301重定向 权重转移,成品网站货源1277哈喽各位#xff0c;我是前端小L。 欢迎来到贪心算法专题第四篇#xff01; 力扣上关于“买卖股票”的题目有一整个系列#xff08;共 6 道#xff09;。其中#xff0c;第 II 题 是最适合用贪心算法解决的。 规则是#xff1a;你可以尽可能地完成更多的交易#xff0…哈喽各位我是前端小L。欢迎来到贪心算法专题第四篇 力扣上关于“买卖股票”的题目有一整个系列共 6 道。其中第 II 题是最适合用贪心算法解决的。规则是你可以尽可能地完成更多的交易多次买卖一支股票但你手里最多只能持有一支股票再次购买前必须卖出之前的。力扣 122. 买卖股票的最佳时机 IIhttps://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/题目分析输入价格数组prices。目标通过多次买卖获得最大利润。例子[7, 1, 5, 3, 6, 4]在第 2 天价格1买入第 3 天价格5卖出赚4。在第 4 天价格3买入第 5 天价格6卖出赚3。总利润4 3 7。核心思维利润分解大家可能会想我是不是要找到一个局部的最低点买入然后再找一个局部的最高点卖出 比如1 - 5我是不是应该持有 4 天贪心思维的魔法我们可以把“长线的利润”分解为“每天的利润”。 假如第 0 天买第 3 天卖价格是prices[0]和prices[3]。 利润 prices[3] - prices[0]。 数学上它等价于prices[3] - prices[0] (prices[3] - prices[2]) (prices[2] - prices[1]) (prices[1] - prices[0])这意味着“第 0 天买、第 3 天卖”的利润等同于“第 0 天买第 1 天卖” “第 1 天买第 2 天卖” “第 2 天买第 3 天卖”的总和。贪心策略我们只需要遍历数组计算每一天相对于前一天的差值如果差值是正数今天涨了收下这个利润就当昨天买今天卖了。如果差值是负数今天跌了不要我就当没操作。我们不需要考虑什么时候卖出我们只需要把所有的正利润片段收集起来就是全局最大利润算法流程初始化result 0。遍历数组从第 1 天开始下标 1一直到最后。计算差值diff prices[i] - prices[i-1]。贪心收集if (diff 0)result diff。返回result。代码实现 (C)C#include vector using namespace std; class Solution { public: int maxProfit(vectorint prices) { int result 0; // 从第二天开始遍历 for (int i 1; i prices.size(); i) { // 今天的利润 今天的价格 - 昨天的价格 int dailyProfit prices[i] - prices[i-1]; // 贪心策略只收集正利润 // 只要涨了我就赚这笔钱如果跌了我就不参与 if (dailyProfit 0) { result dailyProfit; } } return result; } };深度辨析为什么能这么做有人会问“如果我昨天买了今天涨了我卖了。但明天又涨了我手里没股票了怎么办”别忘了题目规则当天卖出后可以当天立刻买入比如1 - 5 - 10。贪心做法第一段1 - 5赚 4。卖出。第二段5 - 10赚 5。买入再卖出。总赚4 5 9。长线做法1买10卖。总赚10 - 1 9。结果是一样的 所以这种“收集所有正向坡度”的策略在没有交易手续费、没有交易次数限制的情况下是绝对的最优解。深度复杂度分析时间复杂度O(N)只需要遍历一次数组。空间复杂度O(1)只要一个变量。总结化繁为简的智慧这道题展示了贪心算法通过**“数学等价转换”简化问题的能力。 我们将一个需要寻找波峰波谷的复杂决策问题简化成了一个简单的加法问题**。只要p[i] p[i-1]就加就这么简单。下一题预告 如果我们不是在炒股而是在玩**“跳跃游戏”。 给你一个数组每个格子里的数字代表你能向右跳的最大步数**。请问你能否跳到终点 这道题的贪心策略不再是累加收益而是维护一个**“最大覆盖范围”**。只要终点在我的覆盖范围内我就赢了下期见