百度seo新站优化,如何进入公众号,小众电商平台有哪些,网址大全怎么卸载文章目录122. 买卖股票的最佳时机 II描述示例 1示例 2示例 3提示解题思路核心观察关键洞察算法实现方法1#xff1a;贪心算法#xff08;推荐#xff09;方法2#xff1a;动态规划方法3#xff1a;动态规划#xff08;空间优化#xff09;方法4#xff1a;波峰波谷法算…
文章目录122. 买卖股票的最佳时机 II描述示例 1示例 2示例 3提示解题思路核心观察关键洞察算法实现方法1贪心算法推荐方法2动态规划方法3动态规划空间优化方法4波峰波谷法算法分析复杂度对比算法流程图贪心算法证明示例分析动态规划详解状态转移方程状态转移图DP状态表示例实际应用1. 投资策略2. 类似问题3. 实际约束代码实现要点边界条件处理数组越界防护整数溢出考虑练习建议相关题目完整题解代码122. 买卖股票的最佳时机 II
描述
给你一个整数数组 prices 其中 prices[i] 表示某支股票第 i 天的价格。
在每一天你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1
输入prices [7,1,5,3,6,4] 输出7 解释在第 2 天股票价格 1的时候买入在第 3 天股票价格 5的时候卖出, 这笔交易所能获得利润 5 - 1 4。 随后在第 4 天股票价格 3的时候买入在第 5 天股票价格 6的时候卖出, 这笔交易所能获得利润 6 - 3 3。 最大总利润为 4 3 7 。
示例 2
输入prices [1,2,3,4,5] 输出4 解释在第 1 天股票价格 1的时候买入在第 5 天 股票价格 5的时候卖出, 这笔交易所能获得利润 5 - 1 4。 最大总利润为 4 。
示例 3
输入prices [7,6,4,3,1] 输出0 解释在这种情况下, 交易无法获得正利润所以不参与交易可以获得最大利润最大利润为 0。
提示
1 prices.length 3 * 10^40 prices[i] 10^4
解题思路
这道题的核心思想是由于可以进行多次买卖我们需要抓住每一次股价上涨的机会来获得最大利润。
核心观察
无限制交易可以进行任意次数的买卖同一天可以买卖先买再卖或者先卖再买最多持有一股不能同时持有多股目标获得最大总利润
关键洞察
贪心策略只要明天的价格比今天高就今天买入明天卖出。这样可以捕获所有的价格上涨段。
算法实现
方法1贪心算法推荐
func maxProfitGreedy(prices []int) int {maxProfit : 0for i : 1; i len(prices); i {if prices[i] prices[i-1] {maxProfit prices[i] - prices[i-1]}}return maxProfit
}原理累加所有相邻的正收益。
时间复杂度O(n) 空间复杂度O(1)
方法2动态规划
func maxProfitDP(prices []int) int {n : len(prices)dp : make([][2]int, n)dp[0][0] 0 // 不持有股票dp[0][1] -prices[0] // 持有股票for i : 1; i n; i {dp[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]) // 买入}return dp[n-1][0]
}状态定义
dp[i][0]第i天结束后不持有股票的最大利润dp[i][1]第i天结束后持有股票的最大利润
时间复杂度O(n) 空间复杂度O(n)
方法3动态规划空间优化
func maxProfitDPOptimized(prices []int) int {hold : -prices[0] // 持有股票的最大利润sold : 0 // 不持有股票的最大利润for i : 1; i len(prices); i {newSold : max(sold, holdprices[i])newHold : max(hold, sold-prices[i])sold, hold newSold, newHold}return sold
}时间复杂度O(n) 空间复杂度O(1)
方法4波峰波谷法
找到所有的波谷和波峰在波谷买入在波峰卖出。
func maxProfitPeakValley(prices []int) int {i, maxProfit : 0, 0for i len(prices)-1 {// 找波谷for i len(prices)-1 prices[i1] prices[i] {i}valley : prices[i]// 找波峰for i len(prices)-1 prices[i1] prices[i] {i}peak : prices[i]maxProfit peak - valley}return maxProfit
}算法分析
复杂度对比
方法时间复杂度空间复杂度优点缺点贪心算法O(n)O(1)简洁高效易理解需要理解贪心思想动态规划O(n)O(n)状态转移清晰空间开销大动态规划优化O(n)O(1)空间效率高状态维护复杂波峰波谷O(n)O(1)直观易懂代码稍复杂状态机O(n)O(1)逻辑清晰理解成本高
算法流程图
#mermaid-svg-hMCPq7exvBF5hyqV {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-hMCPq7exvBF5hyqV .error-icon{fill:#552222;}#mermaid-svg-hMCPq7exvBF5hyqV .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-hMCPq7exvBF5hyqV .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-hMCPq7exvBF5hyqV .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-hMCPq7exvBF5hyqV .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-hMCPq7exvBF5hyqV .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-hMCPq7exvBF5hyqV .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-hMCPq7exvBF5hyqV .marker{fill:#333333;stroke:#333333;}#mermaid-svg-hMCPq7exvBF5hyqV .marker.cross{stroke:#333333;}#mermaid-svg-hMCPq7exvBF5hyqV svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-hMCPq7exvBF5hyqV .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-hMCPq7exvBF5hyqV .cluster-label text{fill:#333;}#mermaid-svg-hMCPq7exvBF5hyqV .cluster-label span{color:#333;}#mermaid-svg-hMCPq7exvBF5hyqV .label text,#mermaid-svg-hMCPq7exvBF5hyqV span{fill:#333;color:#333;}#mermaid-svg-hMCPq7exvBF5hyqV .node rect,#mermaid-svg-hMCPq7exvBF5hyqV .node circle,#mermaid-svg-hMCPq7exvBF5hyqV .node ellipse,#mermaid-svg-hMCPq7exvBF5hyqV .node polygon,#mermaid-svg-hMCPq7exvBF5hyqV .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-hMCPq7exvBF5hyqV .node .label{text-align:center;}#mermaid-svg-hMCPq7exvBF5hyqV .node.clickable{cursor:pointer;}#mermaid-svg-hMCPq7exvBF5hyqV .arrowheadPath{fill:#333333;}#mermaid-svg-hMCPq7exvBF5hyqV .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-hMCPq7exvBF5hyqV .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-hMCPq7exvBF5hyqV .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-hMCPq7exvBF5hyqV .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-hMCPq7exvBF5hyqV .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-hMCPq7exvBF5hyqV .cluster text{fill:#333;}#mermaid-svg-hMCPq7exvBF5hyqV .cluster span{color:#333;}#mermaid-svg-hMCPq7exvBF5hyqV div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-hMCPq7exvBF5hyqV :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;}是否是否是否开始输入价格数组数组长度 1?返回0初始化利润 0遍历第1天到最后一天今天价格 昨天价格?利润 今天价格 - 昨天价格跳过这一天还有下一天?返回总利润结束贪心算法证明
命题对于任意价格序列贪心策略累加所有正差值能够获得最大利润。
证明
可行性贪心策略产生的交易序列是合法的每次买入后必须卖出才能再次买入最优性任何其他交易策略的利润都不会超过贪心策略
设最优解包含交易 (buy_i, sell_i)其总利润为
profit Σ(sell_i - buy_i)贪心策略的利润为
greedy_profit Σ(prices[i] - prices[i-1]) for all i where prices[i] prices[i-1]可以证明greedy_profit profit
示例分析
示例1prices [7,1,5,3,6,4]
贪心分析
第1天: 7 - 第2天: 1下跌不交易
第2天: 1 - 第3天: 5上涨利润 5-1 4
第3天: 5 - 第4天: 3下跌不交易
第4天: 3 - 第5天: 6上涨利润 6-3 3
第5天: 6 - 第6天: 4下跌不交易总利润 4 3 7可视化
价格走势图7 |●| \5 | ●| \3 | ●---●| \1 | ● ●----------1 2 3 4 5 天数交易策略第2天买入(1) - 第3天卖出(5)利润4第4天买入(3) - 第5天卖出(6)利润3动态规划详解
状态转移方程
dp[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])状态转移图
#mermaid-svg-iYIHgIn8xM5h1Wnc {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-iYIHgIn8xM5h1Wnc .error-icon{fill:#552222;}#mermaid-svg-iYIHgIn8xM5h1Wnc .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-iYIHgIn8xM5h1Wnc .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-iYIHgIn8xM5h1Wnc .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-iYIHgIn8xM5h1Wnc .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-iYIHgIn8xM5h1Wnc .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-iYIHgIn8xM5h1Wnc .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-iYIHgIn8xM5h1Wnc .marker{fill:#333333;stroke:#333333;}#mermaid-svg-iYIHgIn8xM5h1Wnc .marker.cross{stroke:#333333;}#mermaid-svg-iYIHgIn8xM5h1Wnc svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-iYIHgIn8xM5h1Wnc defs #statediagram-barbEnd{fill:#333333;stroke:#333333;}#mermaid-svg-iYIHgIn8xM5h1Wnc g.stateGroup text{fill:#9370DB;stroke:none;font-size:10px;}#mermaid-svg-iYIHgIn8xM5h1Wnc g.stateGroup text{fill:#333;stroke:none;font-size:10px;}#mermaid-svg-iYIHgIn8xM5h1Wnc g.stateGroup .state-title{font-weight:bolder;fill:#131300;}#mermaid-svg-iYIHgIn8xM5h1Wnc g.stateGroup rect{fill:#ECECFF;stroke:#9370DB;}#mermaid-svg-iYIHgIn8xM5h1Wnc g.stateGroup line{stroke:#333333;stroke-width:1;}#mermaid-svg-iYIHgIn8xM5h1Wnc .transition{stroke:#333333;stroke-width:1;fill:none;}#mermaid-svg-iYIHgIn8xM5h1Wnc .stateGroup .composit{fill:white;border-bottom:1px;}#mermaid-svg-iYIHgIn8xM5h1Wnc .stateGroup .alt-composit{fill:#e0e0e0;border-bottom:1px;}#mermaid-svg-iYIHgIn8xM5h1Wnc .state-note{stroke:#aaaa33;fill:#fff5ad;}#mermaid-svg-iYIHgIn8xM5h1Wnc .state-note text{fill:black;stroke:none;font-size:10px;}#mermaid-svg-iYIHgIn8xM5h1Wnc .stateLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.5;}#mermaid-svg-iYIHgIn8xM5h1Wnc .edgeLabel .label rect{fill:#ECECFF;opacity:0.5;}#mermaid-svg-iYIHgIn8xM5h1Wnc .edgeLabel .label text{fill:#333;}#mermaid-svg-iYIHgIn8xM5h1Wnc .label div .edgeLabel{color:#333;}#mermaid-svg-iYIHgIn8xM5h1Wnc .stateLabel text{fill:#131300;font-size:10px;font-weight:bold;}#mermaid-svg-iYIHgIn8xM5h1Wnc .node circle.state-start{fill:#333333;stroke:#333333;}#mermaid-svg-iYIHgIn8xM5h1Wnc .node .fork-join{fill:#333333;stroke:#333333;}#mermaid-svg-iYIHgIn8xM5h1Wnc .node circle.state-end{fill:#9370DB;stroke:white;stroke-width:1.5;}#mermaid-svg-iYIHgIn8xM5h1Wnc .end-state-inner{fill:white;stroke-width:1.5;}#mermaid-svg-iYIHgIn8xM5h1Wnc .node rect{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-iYIHgIn8xM5h1Wnc .node polygon{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-iYIHgIn8xM5h1Wnc #statediagram-barbEnd{fill:#333333;}#mermaid-svg-iYIHgIn8xM5h1Wnc .statediagram-cluster rect{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-iYIHgIn8xM5h1Wnc .cluster-label,#mermaid-svg-iYIHgIn8xM5h1Wnc .nodeLabel{color:#131300;}#mermaid-svg-iYIHgIn8xM5h1Wnc .statediagram-cluster rect.outer{rx:5px;ry:5px;}#mermaid-svg-iYIHgIn8xM5h1Wnc .statediagram-state .divider{stroke:#9370DB;}#mermaid-svg-iYIHgIn8xM5h1Wnc .statediagram-state .title-state{rx:5px;ry:5px;}#mermaid-svg-iYIHgIn8xM5h1Wnc .statediagram-cluster.statediagram-cluster .inner{fill:white;}#mermaid-svg-iYIHgIn8xM5h1Wnc .statediagram-cluster.statediagram-cluster-alt .inner{fill:#f0f0f0;}#mermaid-svg-iYIHgIn8xM5h1Wnc .statediagram-cluster .inner{rx:0;ry:0;}#mermaid-svg-iYIHgIn8xM5h1Wnc .statediagram-state rect.basic{rx:5px;ry:5px;}#mermaid-svg-iYIHgIn8xM5h1Wnc .statediagram-state rect.divider{stroke-dasharray:10,10;fill:#f0f0f0;}#mermaid-svg-iYIHgIn8xM5h1Wnc .note-edge{stroke-dasharray:5;}#mermaid-svg-iYIHgIn8xM5h1Wnc .statediagram-note rect{fill:#fff5ad;stroke:#aaaa33;stroke-width:1px;rx:0;ry:0;}#mermaid-svg-iYIHgIn8xM5h1Wnc .statediagram-note rect{fill:#fff5ad;stroke:#aaaa33;stroke-width:1px;rx:0;ry:0;}#mermaid-svg-iYIHgIn8xM5h1Wnc .statediagram-note text{fill:black;}#mermaid-svg-iYIHgIn8xM5h1Wnc .statediagram-note .nodeLabel{color:black;}#mermaid-svg-iYIHgIn8xM5h1Wnc .statediagram .edgeLabel{color:red;}#mermaid-svg-iYIHgIn8xM5h1Wnc #dependencyStart,#mermaid-svg-iYIHgIn8xM5h1Wnc #dependencyEnd{fill:#333333;stroke:#333333;stroke-width:1;}#mermaid-svg-iYIHgIn8xM5h1Wnc :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;}不操作买入股票不操作卖出股票不持有股票持有股票DP状态表示例
对于 prices [7,1,5,3,6,4]
天数价格不持有股票持有股票决策070-7初始状态110-1在第1天买入更优254-1第2天卖出获利43341第3天买入4671第4天卖出获利35473保持不持有状态
实际应用
1. 投资策略
短线交易频繁买卖获取价差波段操作在价格波动中获利算法交易程序化交易系统
2. 类似问题
买卖股票的最佳时机系列题目背包问题的变种区间调度问题
3. 实际约束
在实际投资中还需考虑
交易手续费税收影响市场流动性价格滑点
代码实现要点
边界条件处理
if len(prices) 1 {return 0 // 少于2个价格无法交易
}数组越界防护
for i : 1; i len(prices); i { // 从第2个元素开始// 安全访问 prices[i] 和 prices[i-1]
}整数溢出考虑
对于极大数据考虑使用 int64 或添加溢出检查。
练习建议
理解贪心思想为什么累加所有正差值是最优的掌握状态转换DP中两个状态如何相互转换空间优化技巧如何从O(n)优化到O(1)扩展思考如果有交易手续费怎么办变种练习限制交易次数的情况如何处理
相关题目
121. 买卖股票的最佳时机只能交易一次123. 买卖股票的最佳时机 III最多交易两次188. 买卖股票的最佳时机 IV最多交易k次309. 最佳买卖股票时机含冷冻期含冷冻期714. 买卖股票的最佳时机含手续费含手续费
完整题解代码
package mainimport (fmttime
)// 方法1贪心算法 - 抓住每一次上涨机会
// 时间复杂度O(n)空间复杂度O(1)
func maxProfitGreedy(prices []int) int {if len(prices) 1 {return 0}maxProfit : 0// 只要第二天比第一天价格高就在第一天买入第二天卖出for i : 1; i len(prices); i {if prices[i] prices[i-1] {maxProfit prices[i] - prices[i-1]}}return maxProfit
}// 方法2动态规划
// 时间复杂度O(n)空间复杂度O(n)
func maxProfitDP(prices []int) int {if len(prices) 1 {return 0}n : len(prices)// dp[i][0] 表示第i天不持有股票的最大利润// dp[i][1] 表示第i天持有股票的最大利润dp : make([][2]int, n)// 初始状态dp[0][0] 0 // 第0天不持有股票利润为0dp[0][1] -prices[0] // 第0天买入股票利润为-prices[0]for i : 1; i n; i {// 第i天不持有股票可能是前一天就不持有或者前一天持有今天卖出dp[i][0] max(dp[i-1][0], dp[i-1][1]prices[i])// 第i天持有股票可能是前一天就持有或者前一天不持有今天买入dp[i][1] max(dp[i-1][1], dp[i-1][0]-prices[i])}// 最后一天不持有股票肯定比持有股票利润更大return dp[n-1][0]
}// 方法3动态规划空间优化
// 时间复杂度O(n)空间复杂度O(1)
func maxProfitDPOptimized(prices []int) int {if len(prices) 1 {return 0}// 只需要记录当前的状态不需要整个数组hold : -prices[0] // 持有股票的最大利润sold : 0 // 不持有股票的最大利润for i : 1; i len(prices); i {newSold : max(sold, holdprices[i]) // 今天卖出newHold : max(hold, sold-prices[i]) // 今天买入sold newSoldhold newHold}return sold
}func max(a, b int) int {if a b {return a}return b
}func main() {testCases : [][]int{{7, 1, 5, 3, 6, 4}, // 预期输出: 7{1, 2, 3, 4, 5}, // 预期输出: 4{7, 6, 4, 3, 1}, // 预期输出: 0{1, 2, 1, 2, 1}, // 预期输出: 2{5}, // 预期输出: 0{}, // 预期输出: 0}fmt.Println( 买卖股票的最佳时机 II - 多种解法测试 )fmt.Println()methods : []struct {name stringfn func([]int) int}{{贪心算法, maxProfitGreedy},{动态规划, maxProfitDP},{动态规划(优化), maxProfitDPOptimized},}for i, testCase : range testCases {fmt.Printf(测试用例 %d: %v\n, i1, testCase)for _, method : range methods {start : time.Now()result : method.fn(testCase)duration : time.Since(start)fmt.Printf( %s: %d (用时: %v)\n, method.name, result, duration)}fmt.Println()}// 算法思路演示fmt.Println( 算法思路演示 )demonstrateGreedyApproach([]int{7, 1, 5, 3, 6, 4})
}func demonstrateGreedyApproach(prices []int) {fmt.Printf(\n贪心算法思路演示:\n)fmt.Printf(价格数组: %v\n, prices)maxProfit : 0transactions : []string{}for i : 1; i len(prices); i {if prices[i] prices[i-1] {profit : prices[i] - prices[i-1]maxProfit profittransaction : fmt.Sprintf(第%d天买入(%d) - 第%d天卖出(%d), 利润: %d, i, prices[i-1], i1, prices[i], profit)transactions append(transactions, transaction)}}fmt.Println(交易记录:)for _, transaction : range transactions {fmt.Printf( %s\n, transaction)}fmt.Printf(总利润: %d\n, maxProfit)
}
