分享一个简单但挺有意思的算法题2-贪心-单调栈-动态规划数据结构与算法

1. 题目描述 LeetCode 122.买卖股票的最佳时机 II

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。返回你能获得的最大利润。

示例：

*输入：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-贪心-单调栈-动态规划】这道题常见且并不难，有意思的是解法也非常多，尤其适合入门级别的单调栈和动态规划
2. 贪心算法这是最容易想到的解法，因为交易次数不受限，只需要在股价的每个上坡底部买入，坡顶卖出，则一定是利益最大化的

function maxProfit(prices){ let ans = 0; for (let i = 0; i < prices.length - 1; i++) { if (prices[i + 1] > prices[i]) {// 在上坡过程中，【每天都交易】和【底部买入，坡顶卖出】是完全等效的(忽略手续费) ans += (prices[i + 1] - prices[i]); } } return ans }

3. 单调栈单调栈顾名思义是单调递增/减的一种栈结构，股价的上坡在数据结构上的表示，其实就是一个递增的单调栈，我们只要依次找到所有的上坡，此时栈顶减去栈底，则是单次上坡的最大利润

function maxProfit(prices){ //这里只末尾+0就够了 prices.push(0) //前后+0，是单调栈很常见的处理措施，确保起止元素一定能形成首个坡，终止末个的坡 let ans = 0 let stack = []for (let i = 0; i < prices.length; i++) { //stack[stack.length - 1] 单调栈栈顶，即本次上坡最大值 if(stack.length > 0 && prices[i] < stack[stack.length - 1]){ //栈顶 let top= stack[stack.length - 1] //栈底 let bottom = stack[0] ans += top - bottom stack = []//清栈 } stack.push(prices[i]) } return ans }

这里主要讲单调栈，所以保留了栈结构，实际本题比较简单，只需记录栈顶栈底即可
简化后:

function maxProfit(prices){ prices.push(0) let ans= 0 let top= prices[0] let bottom = prices[0]for (let i = 0; i < prices.length; i++) { if(prices[i] >= top){ top = prices[i] }else{ ans += top - bottom top = bottom = prices[i] } } return ans }

本题是单调栈最基础的应用，复杂点的比如接雨水，柱状图中最大的矩形，都是单调栈的应用场景，总之，单调栈是一个强大有趣的数据结构。

4. 动态规划不难得出每日只有持仓空仓两种状态：

对于今日持仓状态，今天账号的最大余额为【昨日持仓】和【昨日空仓 - 今日股价】(买入所以扣钱)中的较大值

对于今日空仓状态，今天账号的最大余额为【昨日空仓】和【昨日持仓 + 今日股价】(卖出所以加钱)中的较大值

最后一天平仓，即空仓状态下账号余额就是最大收益
得到状态转移方程：

$$对于持仓状态 f(i)_持 = max( f(i-1)_持, + f(i-1)_空 - price[i] )$$

$$对于空仓状态 f(i)_空 = max( f(i-1)_空, + f(i-1)_持 + price[i] )$$

function maxProfit(prices){ //最初始的状态 let dp = [] dp.push( { 'positon':-prices[0],//持仓 'short_positon':0//空仓 } ) for (let i = 1; i < prices.length; i++) { let status = { //本次选择持仓，则账户最大金额为max(昨天持仓，昨天空仓-今日股价) 'positon':Math.max(dp[i-1].positon, dp[i-1].short_positon - prices[i]), //本次选择空仓，则账户最大金额为max(昨天空仓，昨天持仓+今日股价) 'short_positon': Math.max(dp[i-1].short_positon, dp[i-1].positon + prices[i]) } } return dp[prices.length-1].short_positon }

由于只用得到昨日的数据，故而不用储存每日的持仓状态，只需要记录昨天即可，
简化后:

function maxProfit(prices){ //最初始的状态 let positon= -prices[0] //持仓 let short_positon = 0 //空仓for (let i = 1; i < prices.length; i++) { let new_positon= Math.max(positon, short_positon - prices[i]) let new_short_positon = Math.max(short_positon, positon + prices[i]) positon= new_positon short_positon= new_short_positon } return short_positon }