LeetCode--买卖股票的最佳时机系列

港控/mmm° 2023-07-15 13:25 8阅读 0赞

## 买卖股票的最佳时机I ##

通过一次交易，获得最大利润，可以使用栈维护一个上升子序列，若第i天的价格大于栈顶元素，入栈，并计算栈底和栈顶的差值，记录这个差值；

若第i天的价格小于栈顶元素，循环出栈，直到大于栈顶元素或者栈为空；

type Stack struct {
    	Sli []int
    	Len int
    }
    
    func (s *Stack) Push(val int) {
    	s.Sli[s.Len] = val
    	s.Len++
    }
    
    func (s *Stack) Pop() {
    	s.Len--
    }
    
    func (s *Stack) Top() int {
    	if s.Len == 0 {
    		return 0
    	}
    	return s.Sli[s.Len-1]
    }
    
    func (s *Stack) Start() int {
    	return s.Sli[0]
    }
    
    func maxProfit(prices []int) int {
    	stack := &Stack{make([]int, 100), 0}
    	ans := 0
    	for i, v := range prices {
    		if i == 0 {
    			stack.Push(v)
    			continue
    		}
    		if v <= stack.Top() { //维护栈为上升子序列
    			for ;stack.Len>0 && stack.Top() >= v ; {
    				stack.Pop()
    			}
    			stack.Push(v)
    		} else {
    			stack.Push(v) 
    			if ans < stack.Top() - stack.Start() { //计算栈尾与栈首差值
    				ans = stack.Top() - stack.Start()
    			}
    		}
    	}
    	return ans
    }

优化方案：有以上逻辑，可以看出维护上升子序列的栈，只是为了获取第i天之前，最小的价格，由此可以使用dp\[i\]来维护第i天之前的最小价格，即dp\[i\] = Min(dp\[i-1\], prices\[i\])，代码如下：

func maxProfit(prices []int) int {
    	dp := make([]int, 100000)
    	ans := 0
    	dp[0] = math.MaxInt32
    	for i, v := range prices {
    		ans = Max(ans, v - dp[i])
    		dp[i+1] = Min(dp[i], v) //维护i天之前的最小价格
    	}
    	return ans
    }
    
    func Max(i, j int) int {
    	if i > j {
    		return i
    	}
    	return j
    }
    
    func Min(i, j int) int {
    	if i > j {
    		return j
    	}
    	return i
    }

## 买卖股票的最佳时机II ##

因为不限制交易次数，而获得最大利润。这个问题可以转换为找出连续上升子序列，子序列的最大值与最小值的差，为一次交易的利润。由此化解为相邻两天价格的差值，若差值大于0，便是交易一次利润。

举例:1, 4, 7, 5, 2, 5

连续上升子序列为\[1，4，7\]和\[2，5\]，对于第一个序列事实上，就是1买入，7卖出

func maxProfit(prices []int) int {
        ans := 0
    	for i:=0; i<len(prices)-1; i++ {
    		if prices[i] < prices[i+1] {
    			ans = ans + prices[i+1] - prices[i]
    		}
    	}
    	return ans
    }

## 买卖股票的最佳时机III ##

先说说暴力解法（超时）：深度搜素DFS，主要有三种情况：1、买入第i天的股票；2、卖出之前持有的股票；3、不操作

func Max(i, j int) int {
    	if i > j {
    		return i
    	}
    	return j
    }
    
    func Min(i, j int) int {
    	if i > j {
    		return j
    	}
    	return i
    }
    
    var ans int
    func Dfs(prices []int, pos int, mairuCnt, maichuCnt int) (int) {
    	if maichuCnt > 2 || mairuCnt > 2 || pos >= len(prices) {
    		return 0
    	}
        //买入或者不买
    	if maichuCnt == mairuCnt {
    		return Max(Dfs(prices, pos+1, mairuCnt, maichuCnt), Dfs(prices, pos+1, mairuCnt+1, maichuCnt) - prices[pos])
    	}
    	//卖出或者不买
    	if mairuCnt - maichuCnt == 1 {
    		return Max(Dfs(prices, pos+1, mairuCnt, maichuCnt), Dfs(prices, pos+1, mairuCnt, maichuCnt+1) + prices[pos])
    	}
    	return 0
    }
    
    func maxProfit(prices []int) int {
    	ans := Dfs(prices, 0,0, 0)
    	return ans
    }

在此基础上，我们可以推出动态规划的解法

定义：dp\[i\]\[j\]\[k\] 表示第i天，j（持有：1或不持有：0）状态下，k次交易所得的最大利润

状态转移方程

1.第i天不持有股票状态下，经过k次交易，获得的最大利润；（mairuCnt-maichuCnt是是否持有股票的判断）

dp\[i\]\[0\]\[k\] = Max(dp\[i-1\]\[0\]\[k\], dp\[i-1\]\[1\]\[k-1\] + prices\[i\])

a.前一天的不持有股票状态的利润

b.今天卖出，前一天持有的股票获得利润+卖出价格

2.第i天持有股票状态下，经过k次交易，获得最大利润

dp\[i\]\[1\]\[k\] = Max(dp\[i-1\]\[1\]\[k\], dp\[i-1\]\[0\]\[k\] - prices\[i\])

a.前一天的持有股票状态的利润

b.今天买入，前一天不持有的股票获得利润-买入价格

初始化：对于第1天，持有股票的状态，不管交易几次都是刚买入第1天股票，为了之后，持有之前还是持有之后的，获得利润最大

dp\[0\]\[1\]\[k\] = -prices\[0\]

特殊条件：对于交易0次，持有股票状态的dp值，都是持有i天之前最小的价格，才能获得最大的利润

代码如下:

func Max(i, j int) int {
    	if i > j {
    		return i
    	}
    	return j
    }
    
    func maxProfit(prices []int) int {
    	pLen := len(prices)
            k := 2
    	if pLen < 1 {
    		return 0
    	}
    	dp := make([][2][3]int, pLen+10)
    	for i := 0; i <= k; i++ {
    		dp[0][1][i] = -prices[0] //初始化
    	}
    	for i:=1; i<pLen; i++ {
    		dp[i][1][0] = Max(dp[i-1][1][0], -prices[i])  //特殊条件
    		for kp:=1; kp<=k; kp++ {
    			dp[i][0][kp] = Max(dp[i-1][1][kp-1]+prices[i], dp[i-1][0][kp]) //卖出
    			dp[i][1][kp] = Max(dp[i-1][0][kp] - prices[i], dp[i-1][1][kp]) //买入
    		}
    	}
    	return dp[pLen-1][0][k]
    }

## 买卖股票的最佳时机IV ##

题目在III的基础的两次，改为了交易k次后获得最大利润，实际上变为了III的解法，但是这个问题，有一个坑，按III的代码提交会超出内存，一定是存在k的值很大的情况。

大家想想，一次买入，一次卖出，为一次完整交易，i天总的交易次数，事实上只有i/2次；但是k为交易次数，交易次数若很大，大于i/2次，问题就退化成了（买卖股票的最佳时机II）问题，由此特判一下，就Ok了

代码如下：

func Max(i, j int) int {
    	if i > j {
    		return i
    	}
    	return j
    }
    
    func maxProfit(k int, prices []int) int {
    	pLen := len(prices)
    	if pLen < 1 {
    		return 0
    	}
        //买卖股票的最佳时机II
        if pLen/2 < k {
    		ans := 0
    		for i:=0; i<len(prices)-1; i++ {
    			if prices[i] < prices[i+1] {
    				ans = ans + prices[i+1] - prices[i]
    			}
    		}
    		return ans
    	}
        //买卖股票的最佳时机III
    	dp := make([][2][10010]int, pLen+10)
    	for i := 0; i <= k; i++ {
    		dp[0][1][i] = -prices[0] //初始化
    	}
    	for i:=1; i<pLen; i++ {
    		dp[i][1][0] = Max(dp[i-1][1][0], -prices[i]) 
    		for kp:=1; kp<=k; kp++ {
    			dp[i][0][kp] = Max(dp[i-1][1][kp-1]+prices[i], dp[i-1][0][kp]) //卖出
    			dp[i][1][kp] = Max(dp[i-1][0][kp] - prices[i], dp[i-1][1][kp]) //买入
    		}
    	}
    	return dp[pLen-1][0][k]
    }