题目
121. 买卖股票的最佳时机
给定一个数组
prices
，它的第
i
个元素
prices[i]
表示一支给定股票第
i
天的价格。
你只能选择
某一天
买入这只股票，并选择在
未来的某一个不同的日子
卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回
0
。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
-
1 <= prices.length <= 105
-
0 <= prices[i] <= 104
思路与代码
股票问题一共有六道题，链接如下：
-
121. 买卖股票的最佳时机
-
122. 买卖股票的最佳时机 II
-
123. 买卖股票的最佳时机 III
-
188. 买卖股票的最佳时机 IV
-
309. 最佳买卖股票时机含冷冻期
-
714. 买卖股票的最佳时机含手续费
每个问题都有优质的题解，但是大多数题解没有建立起这些问题之间的联系，也没有给出股票问题系列的通解。这篇文章给出适用于全部股票问题的通解，以及对于每个特定问题的特解。
方法一：暴力法
package main
import "fmt"
func maxProfit(prices []int) int {
n, ans := len(prices), 0
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
ans = max(ans, prices[j]-prices[i])
}
}
return ans
}
func main() {
nums := []int{7, 1, 5, 3, 6, 4}
res := maxProfit(nums)
fmt.Println(res)
}
方法二：一次遍历
如果可以在历史最低点买入股票就好了，然后在最高点卖出。具体作法是用一个大数置换出数组中的小数（或者判断是否是第一天，或者跳过第一天），这样，每次循环都比较就得到了
miniprice
。
func maxProfit(prices []int) int {
miniprice, maxprofit := math.MaxInt64, 0
for i := 0; i < len(prices); i++ {
if (prices[i] < miniprice) {
miniprice = prices[i]
} else if (prices[i]-miniprice > maxprofit) {
maxprofit = prices[i] - miniprice
}
}
return maxprofit
}
func main() {
nums := []int{7, 1, 5, 3, 6, 4}
res := maxProfit(nums)
fmt.Println(res)
}
