Golang算法之买卖股票的最佳时机

发表于 | 更新于 | 分类于 | 浏览数
| 字数统计 972

买卖股票的最佳时机，简单难度，leetcode地址：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock

1.描述

给定一个数组 prices ，它的第i个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

1
2
3
4
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2:

1
2
3
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

2.题解

方法一: 暴力循环

leetcode上面很多题都可以使用暴力循环这种方式解决，毕竟没有什么是循环遍历解决不了的，只是效率问题。

这道题也不例外，我们只需2层循环遍历，依次计算不同买卖天之间的利润，求最大值就行，代码逻辑朴实无华！

参考代码:

1
2
3
4
5
6
7
8
9
10
11
func maxProfit(prices []int) int {
    max := 0
    for i := 0; i < len(prices); i++ {
        for j := i + 1; j < len(prices); j++ {
            if p := prices[j] - prices[i]; p > max {
                max = p
            }
        }
    }
    return max
}

然而，这段代码在leetcode里面提交运行超时，因为测试用例里面有一个超长的数组，服了！

方法二: 动态规划

要看明白这个解法，得换个思路，假设我们知道哪天价格最低，我们就可以在那天买，然后在价格最高那天卖出。

假如计划在第 i 天卖出股票，那么最大利润的差值一定是在[0, i-1] 之间选最低点买入；所以遍历数组，依次求每个卖出时机的的最大差值，再从中取最大值。

这个思路结合下面这段代码看，比较有效果：

1
2
3
4
5
6
7
8
9
10
11
12
func maxProfit(prices []int) int {
    minPrice := prices[0]
    maxProfit := 0
    for i := 0; i < len(prices); i++ {
        if prices[i] < minPrice {
            minPrice = prices[i]
        }else if prices[i] - minPrice > maxProfit {
            maxProfit = prices[i] - minPrice
        }
    }
    return maxProfit
}

以[7,1,5,3,6,4]为例，我们手动推导一次：

1
2
3
4
5
6
7
minPrice = 7， maxProfit = 0
i = 0, 7 < 7? 不成立，7-7 > 0?  不成立, minPrice = 7， maxProfit = 0
i = 1, 1 < 7? 已成立，                 minPrice = 1， maxProfit = 0
i = 2, 5 < 1? 不成立，5-1 > 0?  已成立, minPrice = 1， maxProfit = 4
i = 3, 3 < 1? 不成立，3-1 > 4?  不成立, minPrice = 1， maxProfit = 4
i = 4, 6 < 1? 不成立，6-1 > 4?  已成立, minPrice = 1， maxProfit = 5
i = 5, 4 < 1? 不成立，4-1 > 4?  不成立, minPrice = 1， maxProfit = 5

首先，我们定义了最低价格和最大利润2个变量，其中最低价格默认为第一个元素。 然后，依次遍历数组，把每个元素的值和最低价格做比较，有3种结果：

一、如果元素值小于最低价格，那么就更新最低价格

二、如果元素值等于最低价格，那么就不做任何操作

三、如果元素值大于最低价格，说明此时有利可图，我们就算一下利润是多少，如果利润比之前利润大，那么就更新利润

在整个计算过程中，我们动态的更新了最低价格和最大利润，最终得到的结果就是最大利润。