Leetcode题解（7）：股票问题
I
题目很简单，所以直接写了。思路就是遍历数组，维护一个最小值，以及一个最大差值。在遍历过程中不断计算差值，如果当前值比最小值小则更新最小值，如果当前差值比最大差值大则更新差值。
func maxProfit(prices []int) int {
min, res := prices[0], 0
for _, v := range prices {
if v < min {
min = v
} else if res < v - min {
res = v - min
}
}
return res
}
II
与上一题不同的是这次可以多次购买，但是同样很简单，只要差值是正数就可以直接加在结果上。
func maxProfit(prices []int) int {
min, res := prices[0], 0
for _, v := range prices {
if v < min {
min = v
} else {
res += v-min
min = v
}
}
return res
}
我们可以把第二题看成维护两个状态，买入 $buy$ 和卖出 $sell$ ，从而第二题可以这样实现：
func maxProfit(prices []int) int {
buy, sell := math.MinInt32, 0
for _, v := range prices {
buy = max(buy, sell-v)
sell = buy + v
}
return sell
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
$buy$ 表示买入股票，更新规则可以这样理解：
- 如果当前买入的股票比现在的股票便宜，也即 $buy > sell-v$ ，则不更新
- 如果当前买入的股票比现在的股票贵，也即 $buy < sell-v$ ，则更新
而 $sell$ 表示卖出股票，可以发现我们只是简单的为其赋值 $buy+v$ 。如果不在 $buy$ 更新后再更新，就代表着没有考虑今天的股票价格，如果今天的股票价格要小于上次买入的价格，那么就会带来亏损，从而达不到最大的收益。当然，第二题也可以采用下面这种更新方式：
buy, sell = max(buy, sell-v), max(sell, buy+v)
采用上面这种更新方式，当发现在当前卖出之前买入的股票会导致亏损，也就是 $sell > buy+v$ 时，就选择不更新。
III
难度突然骤升，但是还是一样的解法。遍历数组，维护四个变量：第一次买入、第一次卖出、第二次买入和第二次卖出，在遍历的过程中尝试将每个数分别作为第一次买入、第一次卖出、第二次买入和第二次卖出的结果，然后取最大值。
func maxProfit(prices []int) int {
var buy1 = math.MinInt32
var buy2 = math.MinInt32
var sell1 = 0
var sell2 = 0
for _, v := range prices {
buy1 = max(buy1, -v)
sell1 = max(sell1, buy1+v)
buy2 = max(buy2, sell1-v)
sell2 = max(sell2, buy2+v)
}
return sell2
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
IV
其实跟上面一道题一样，只是这次可以多次交易而已，还有注意下对 $0$ 值的处理就行了。
func maxProfit(k int, prices []int) int {
if k == 0 {
return 0
}
buy := make([]int, k)
sell := make([]int, k)
for i, _ := range buy {
buy[i] = math.MinInt32
}
for _, v := range prices {
for i, _ := range buy {
if i == 0 {
buy[i] = max(buy[i], -v)
} else {
buy[i] = max(buy[i], sell[i-1]-v)
}
sell[i] = max(sell[i], buy[i]+v)
}
}
return sell[k-1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
V
这道题其实就是在第二题的基础上多加了个冷冻期的状态，我们可以把之前的 $sell$ 拆为两个状态，从而实现方式为：
func maxProfit(prices []int) int {
buy, sell1, sell2 := math.MinInt32, 0, 0
for _, v := range prices {
buy, sell1, sell2 = max(buy, sell2-v), buy+v, max(sell1, sell2)
}
return max(sell1, sell2)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
比较疑惑的一点就是为什么第二题的 $sell$ 要在 $buy$ 更新后才更新而这一题却不用，而这个问题的关键在于新增的变量 $sell2$ 。 这一道题我们采用了三个变量，其中 $buy$ 依旧是买入的意思，而 $sell1$ 表示卖出当前持有的股票并进入冷冻期，$sell2$ 表示冷冻期结束。$sell2$ 采用的更新方式是与 $sell1$ 进行比较，如果 $sell1$ 产生了亏损，则不会出售。
当然也可以采用下面的更新方式，依旧是正确的：
func maxProfit(prices []int) int {
buy, sell1, sell2 := math.MinInt32, 0, 0
for _, v := range prices {
buy, sell1, sell2 = max(buy, sell2-v), max(sell1, buy+v), sell1
}
return sell1
}
可能这种方式比上面的更好理解，但是本质还是一样的。
VI
有了之前题目作准备，这道题肯定已经没啥难度了，直接秒了。
func maxProfit(prices []int, fee int) int {
buy, sell := math.MinInt32, 0
for _, v := range prices {
buy = max(buy, sell-v-fee)
sell = max(sell, buy+v)
}
return sell
}
func max(a, b int) int {
if a > b {
return a
}
return b
}