关于数据结构与算法:分享一个简单但挺有意思的算法题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. 贪婪算法

这是最容易想到的解法，因为交易次数不受限，只须要在股价的每个上坡底部买入，坡顶卖出，则肯定是利益最大化的

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
}

动静布局是一个弱小乏味的算法。