免费网络推广网站大全校园推广

免费网络推广网站大全,校园推广,电脑上不了建设厅网站,做流量网站挂广告还能挣钱吗题目描述给定一个整数数组 prices#xff0c;其中 prices[i] 表示某支股票第 i 天的价格。在每一天#xff0c;你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。然而#xff0c;你可以在 同一天 多次买卖该股票#xff0c;但要确保你持有的股票不…题目描述给定一个整数数组prices其中prices[i]表示某支股票第i天的价格。在每一天你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。然而你可以在同一天多次买卖该股票但要确保你持有的股票不超过一股。返回你能获得的最大利润。示例 1text输入prices [7,1,5,3,6,4] 输出7 解释在第 2 天买入第 3 天卖出利润 5-14 在第 4 天买入第 5 天卖出利润 6-33 总利润 437示例 2text输入prices [1,2,3,4,5] 输出4 解释在第 1 天买入第 5 天卖出利润 5-14 注意你不能在第 1 天和第 2 天连续买入股票示例 3text输入prices [7,6,4,3,1] 输出0 解释没有交易完成最大利润为 0解法一贪心算法面试推荐⭐核心思想只要今天的价格比昨天高就昨天买入今天卖出。虽然这看起来像是频繁交易但数学上等价于在价格上升波段的最低点买入、最高点卖出。算法步骤从第二天开始遍历价格数组计算当天与前一天的价格差如果价格差为正当天价格 前一天价格则累加到总利润中返回总利润代码实现javaclass Solution { public int maxProfit(int[] prices) { int profit 0; for (int i 1; i prices.length; i) { int diff prices[i] - prices[i - 1]; if (diff 0) { profit diff; } } return profit; } }复杂度分析时间复杂度O(n)只需遍历一次数组空间复杂度O(1)只使用了常数级别的额外空间为什么这是正确的考虑价格序列 [1, 3, 5]贪心算法第1天买入第2天卖出利润2第2天买入第3天卖出利润2总利润4最优策略第1天买入第3天卖出总利润4两种策略结果相同因为 (5-1) (3-1) (5-3)解法二动态规划通用解法核心思想定义两个状态dp[i][0]第i天结束时不持有股票的最大利润dp[i][1]第i天结束时持有股票的最大利润状态转移方程textdp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i]) // 保持空仓或卖出 dp[i][1] max(dp[i-1][1], dp[i-1][0] - prices[i]) // 保持持有或买入代码实现javaclass Solution { public int maxProfit(int[] prices) { int n prices.length; int[][] dp new int[n][2]; dp[0][0] 0; // 第一天不持有股票 dp[0][1] -prices[0]; // 第一天持有股票需要买入 for (int i 1; i n; i) { dp[i][0] Math.max(dp[i-1][0], dp[i-1][1] prices[i]); dp[i][1] Math.max(dp[i-1][1], dp[i-1][0] - prices[i]); } return dp[n-1][0]; // 最后一天不持有股票时利润最大 } }空间优化版本javaclass Solution { public int maxProfit(int[] prices) { int hold -prices[0]; // 持有股票的最大利润 int notHold 0; // 不持有股票的最大利润 for (int i 1; i prices.length; i) { int prevHold hold; hold Math.max(hold, notHold - prices[i]); notHold Math.max(notHold, prevHold prices[i]); } return notHold; } }复杂度分析时间复杂度O(n)空间复杂度未优化版本 O(n)优化版本 O(1)解法三峰谷法直观理解核心思想寻找价格序列中的连续上升波段在每个波段的谷底买入、峰顶卖出。算法步骤初始化利润为0指针i从0开始寻找价格低谷价格开始上升的点寻找价格高峰价格开始下降的点计算峰谷差值并累加到利润重复直到遍历完整个数组代码实现javaclass Solution { public int maxProfit(int[] prices) { int profit 0; int i 0; int n prices.length; while (i n - 1) { // 寻找低谷价格停止下降的点 while (i n - 1 prices[i] prices[i 1]) { i; } int valley prices[i]; // 寻找高峰价格停止上升的点 while (i n - 1 prices[i] prices[i 1]) { i; } int peak prices[i]; profit peak - valley; } return profit; } }复杂度分析时间复杂度O(n)每个元素最多被访问两次空间复杂度O(1)面试推荐写法首推贪心算法 ✅原因代码最简洁仅5-7行时间空间复杂度最优容易理解和解释面试中快速写出并分析正确性面试回答模板这道题可以使用贪心算法解决。核心思想是只要第二天的价格比第一天高就把这个差价算作利润。虽然看起来像是频繁交易但实际上等价于在价格上升波段中一直持有股票。算法的时间复杂度是O(n)空间复杂度是O(1)。备选动态规划如果面试官要求更通用的解法或者后续问题扩展如含交易费、冷冻期等可以使用动态规划解法。扩展思考如果加上交易手续费每次卖出时扣除手续费javapublic int maxProfit(int[] prices, int fee) { int hold -prices[0]; int notHold 0; for (int i 1; i prices.length; i) { hold Math.max(hold, notHold - prices[i]); notHold Math.max(notHold, hold prices[i] - fee); } return notHold; }如果加上冷冻期卖出后需要等待一天才能买入javapublic int maxProfit(int[] prices) { if (prices.length 1) return 0; int hold -prices[0]; int notHold 0; int coolDown 0; // 冷冻期 for (int i 1; i prices.length; i) { int prevHold hold; hold Math.max(hold, coolDown - prices[i]); coolDown notHold; notHold Math.max(notHold, prevHold prices[i]); } return notHold; }总结解法时间复杂度空间复杂度推荐指数适用场景贪心算法O(n)O(1)⭐⭐⭐⭐⭐面试首选代码简洁高效动态规划O(n)O(1)~O(n)⭐⭐⭐⭐通用性强可扩展峰谷法O(n)O(1)⭐⭐⭐直观理解价格波段关键点贪心算法是本题的最优解法动态规划是解决股票问题的通用框架理解贪心算法的正确性多次买卖的总利润等于所有上升波段差值的和在面试中建议先给出贪心解法然后如果时间允许或面试官要求再讨论动态规划解法以展示你的全面性。