leetcode 121 股票利润 单调栈解法

由于股票利润本质是在求解当前元素，与之前最小值之间的差值，所以维护一个单调递增的栈，入栈的值都为可能为后面买入股票的历史最低值，当遇到比栈顶元素小的元素证明栈顶元素已经没办法成为后面的最小元素了，所以将栈顶元素与栈底元素进行求差值，最后判断得出最大值。
需要注意的是 栈内保存的是下标，需要取对应的数组值

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        stack=[]
        prices.append(0)
        maxvalue=0
        for i in range(len(prices)):
            while stack and prices[stack[-1]]>prices[i]:
                s=stack[-1]
                stack=stack[:-1]
                if not stack:
                    break
                else:
                    maxvalue=max(maxvalue,prices[s]-prices[stack[0]])
            stack.append(i)
        return maxvalue

使用动态规划方法，设置dp数组为二维，一维表示是否在当前节点买入，二维表示价格数组的遍历，如果当前节点不买入，可能是因为之前没有买入，或者上一把买入这一把卖出。而当前节点买入，可能是因为之前就买入了或者今天才买入，买入的时候放入当前价格的反数，便于后续做差。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp=[[0 for _ in range(2)]for _ in range(len(prices))]
        dp[0][0]=0
        dp[0][1]=-prices[0]

        for i in range(1,len(prices)):
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])
            dp[i][1]=max(dp[i-1][1],-prices[i])


        return dp[len(prices)-1][0]

空间优化

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp=[[0 for _ in range(2)]for _ in range(2)]
        dp[0][0]=0
        dp[0][1]=-prices[0]

        for i in range(1,len(prices)):
            dp[i&1][0]=max(dp[(i-1)&1][0],dp[(i-1)&1][1]+prices[i])
            dp[i&1][1]=max(dp[(i-1)&1][1],-prices[i])


        return dp[(len(prices)-1)&1][0]

仅使用两个空间，因为当前值每次参考的都是上一个值的0,1状态，所以可以设置两个值分别代表上一个状态的0，1值即可。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp=[[0 for _ in range(2)]for _ in range(2)]
        dp[0]=0
        dp[1]=-prices[0]

        for i in range(1,len(prices)):
            dp[0]=max(dp[0],dp[1]+prices[i])
            dp[1]=max(dp[1],-prices[i])


        return dp[0]