算法练习第八天——买卖股票的最佳时机
算法练习第八天——买卖股票的最佳时机
买卖股票的最佳时机题目
给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
示例一:
输入: prices = [7,6,5,4,3,2,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
示例二:
输入: prices = [7,2,4,3,1,9,8] 输出: 7 解释: 在第二天买入,第六天卖出,为最大利润7。
解题思路
方法一:一次遍历
我们只要用一个变量记录一个历史最低价格 minvalue,我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minvalue。
因此,我们只需要遍历价格数组一遍,记录历史最低点,然后在每一天考虑这么一个问题:如果我是在历史最低点买进的,那么我今天卖出能赚多少钱?当考虑完所有天数之时,我们就得到了最好的答案。
以下代码以golang为例:
func maxProfit(prices []int) int { minValue := math.MaxInt64 maxValue := 0 for i := 0; i < len(prices); i++ { if prices[i] < minValue { minValue = prices[i] } else if prices[i]-minValue > maxValue { maxValue = prices[i] - minValue } } return maxValue }
该解法复杂度分析
- 时间复杂度:O(n),需要遍历一次。
- 空间复杂度:O(1),只使用了常数个变量。