题目
给定一个数组 prices ,它的第 i 个元素 prices[ i ] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来 的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
规则示例
规则
1 <= prices.length <= 10的5次方
0 <= prices[ i ] <= 10的4次方
示例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。
解题分析一:暴力双循环
两层循环,算出每一天的价格和之后每一天价格的差值,取最大差值,则可以获取到最大利润值。
解题一:暴力双循环
解题分析二:一次遍历,动态规划
该种解法的关键点时,题目只要求算出最大利润,那么利润最大化的前提是:低价买入,高价卖出!那么我们可以只用一次遍历就可以解决该问题,我们声明一个记录最小价格的变量,在遍历过程中如果发现有更低的价格就记录它,之后遍历的每一天如果没有比它更低的价格,那么就认为是可以卖出的日子,我们再用一个变量来记录利润,只有差值大于该利润变量我们才记录它,那么这样遍历一次后,便可以得到最大利润结果!
我们以 [7,1,5,3,6,4] 为例
从分析中得到一些关键信息:
一个记录最小值的变量
一个记录最大利润的变量
一次循环
动态规划的体现时,最小值可能会随着遍历不停的变化
解题二:一次遍历,动态规划
总结
这道题的关键点是从题目中提取有效信息
计算利润不回头
只求最大利润
那么使用一次遍历动态规范方式解题,时间、空间复杂度都较小。
END