1. 题目描述
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。
注意:你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
2. 解题思路
(1)直接遍历
这个题目比较简单,我们需要对股票进行一次买入、一次卖出,卖出在买入之后,并且要计算最大的利润。
这里初始化一个最小值min,和一个最大的结果值max。遍历数组,如果当前数组元素小于最小值民,就更新最小值,始终让其保持最小。如果当前值减去最小值大于最大值,就更新最大值。直到遍历完数组所有的元素,返回最后的结果。
复杂度分析:
- 时间复杂度:O(n),其中n是数组的长度,我们需要将数组遍历一遍
- 空间复杂度:O(1),这里只需要常数空间来储存最小值min和最大结果值max
(2)动态规划
对于这道题,我们可以使用动态规划来解决。这里我们只需要进行一次买入卖出。那到最后交易时,可能会有三种状态:
dp[0]
:一直没有买dp[1]
::到最后只买了一笔,未卖出dp[2]
::到最后只卖了一笔,并卖出
由于第一种状态未进行任何操作,所以可以不用记录。然后我们对后两种状态进行转移:
dp[1] = Math.max(dp[1], -prices[i])
:前一天也是b1状态或者是没有任何操作,今天买入一笔变成b1状态;dp[2] = Math.max(dp[2], dp[1] + prices[i])
:前一天也是s1状态或者是b1状态,今天卖出一笔变成s1状态;
复杂度分析
- 时间复杂度:O(n),其中 n 是数组 prices 的长度。
-
3. 代码实现
(1)直接遍历
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let max = 0
let min = prices[0]
prices.forEach( item => {
if(item < min) min = item
if(item - min > max) max = item - min
})
return max
};
(2)动态规划
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let len = prices.length;
const dp = [0, -prices[0], 0]
for (let i = 1; i < len; i++) {
dp[1] = Math.max(dp[1], -prices[i])
dp[2] = Math.max(dp[2], dp[1] + prices[i])
}
return dp[2];
}
4. 提交结果
(1)直接遍历
(2)动态规划