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
解法
一开始我使用了双指针,简单测试用例可以跑过,当原数组数值非常多的时候,我的算法就超时了,代码如下:
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function (prices) {
let length = prices.length;
const map = [];
for (let i = 0; i < length; i++) {
let start = prices[i];
let end = Math.max(...prices.slice(i, prices.length));
if (end >= start) {
map[i] = end - start;
}
}
return map.length ? Math.max(...map) : 0;
};
1、双指针
评论区的双指针是这样的,他的思路是在迭代的过程中不断更新 min
,然后让当前值减去 min
再和 max
相比较求最大值。相比我上面的操作,他这样子程序就很轻了。我的算法缺点是:
- 每次迭代都 slice 了数组 耗时
- 每次迭代在剩余元素中求了最大值 耗时
- 使用了哈希表
map
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function (prices) {
if (prices === null || prices.length === 0) {
return 0;
}
let min = prices[0];
let max = 0;
for (let i = 1; i < prices.length; i++) {
min = Math.min(prices[i], min);
max = Math.max(prices[i] - min, max);
}
return max;
};
2、栈
使用栈结构存储遍历时的的最小值,如果当前值小于栈顶元素时,栈顶元素出栈并将当前元素推入栈,如果当前元素大于栈顶元素,计算差值,与历史计算的差值相比求取最大值。
其实没必要用栈这个结构来存储,单纯的一个变量也可以啊
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function (prices) {
if (prices === null || prices.length === 0) {
return 0;
}
let max = 0;
const stack = [];
stack.push(prices[0]);
for (let i = 1; i < prices.length; i++) {
if (prices[i] < stack[0]) {
stack.pop();
stack.push(prices[i]);
} else {
max = Math.max(prices[i] - stack[0], max);
}
}
return max;
};
3、参照最大子序和
最大子序和这个概念可用于求算什么没搞清楚, 但是在本题的的计算思路却是惊奇的
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function (prices) {
if (prices == null || prices.length == 0) {
return 0;
}
const len = prices.length;
let max = 0;
let cur = 0;
for (let i = 1; i < len; i++) {
cur = Math.max(cur, 0) + prices[i] - prices[i - 1];
max = Math.max(cur, max);
}
return max;
};
4、暴力循环
评论区的垫底写法, 很显然跟我最开始自己的想法的结果相同:超出时间限制
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function (prices) {
if (prices == null || prices.length == 0) {
return 0;
}
let max = 0;
for (let i = 0; i < prices.length; i++) {
for (let j = i + 1; j < prices.length; j++) {
max = Math.max(prices[j] - prices[i], max);
}
}
return max;
};
5、动态规划
好!到了今天的主角了, 闪亮登场!!!
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function (prices) {
if (prices == null || prices.length == 0) {
return 0;
}
let length = prices.length;
let dp = [[]];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (let i = 1; i < length; i++) {
dp[i] = dp[i] || [];
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
}
return dp[length - 1][0];
};
动态规划空间复杂度优化,降到 O(1)
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function (prices) {
if (prices == null || prices.length == 0) {
return 0;
}
let profit0 = 0,
profit1 = -prices[0];
let length = prices.length;
for (let i = 1; i < length; i++) {
profit0 = Math.max(profit0, profit1 + prices[i]);
profit1 = Math.max(profit1, -prices[i]);
}
return profit0;
};