Leetcode题解(7):股票问题

I

LeetCode121.买卖股票的最佳时机

        题目很简单,所以直接写了。思路就是遍历数组,维护一个最小值,以及一个最大差值。在遍历过程中不断计算差值,如果当前值比最小值小则更新最小值,如果当前差值比最大差值大则更新差值。

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

LeetCode122.买卖股票的最佳时机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$ 表示买入股票,更新规则可以这样理解:

        而 $sell$ 表示卖出股票,可以发现我们只是简单的为其赋值 $buy+v$ 。如果不在 $buy$ 更新后再更新,就代表着没有考虑今天的股票价格,如果今天的股票价格要小于上次买入的价格,那么就会带来亏损,从而达不到最大的收益。当然,第二题也可以采用下面这种更新方式:

buy, sell = max(buy, sell-v), max(sell, buy+v)

        采用上面这种更新方式,当发现在当前卖出之前买入的股票会导致亏损,也就是 $sell > buy+v$ 时,就选择不更新。

III

LeetCode123.买卖股票的最佳时机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

LeetCode188.买卖股票的最佳时机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

LeetCode309.最佳买卖股票时机含冷冻期

        这道题其实就是在第二题的基础上多加了个冷冻期的状态,我们可以把之前的 $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

LeetCode714.买卖股票的最佳时机含手续费

        有了之前题目作准备,这道题肯定已经没啥难度了,直接秒了。

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
}

Leetcode题解(7):股票问题