暴力
解题思路
暴力寻找找最优间距了；
超时；
复杂度
-
时间复杂度：
O(n^2)； -
空间复杂度：
O(1)；
代码实现
var maxProfit = function (prices) {
let max = 0;
for (let i = 0; i < prices.length; i++) {
for (let j = i + 1; j < prices.length; j++) {
max = Math.max(max, prices[j] - prices[i]);
}
}
return max;
};
贪心
解题思路
因为股票就买卖一次，那么贪心的想法很自然就是取最左最小值，取最右最大值，那么得到的差值就是最大利润；
复杂度
-
时间复杂度：
O(n)； -
空间复杂度：
O(1)；
代码实现
var maxProfit = function (prices) {
if (prices.length === 0) return 0;
let min = prices[0]; // 最低买点
let max = 0; // 最大收入
// 一次遍历找到最高点和最低点
for (let curr of prices) {
// 最佳买点，买入点最低
min = Math.min(min, curr);
max = Math.max(max, curr - min);
}
return max;
};
动态规划
解题思路
确定 dp 数组以及下标的含义：dp[i][j] 表示天数 [0, i] 区间里，下标 i 这一天状态为 j 的时候能够获得的最大利润，其中：
- j = 0，表示当前不持股；
- j = 1，表示当前持股；
确定递推公式：
- dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])：规定了今天 不持股，有以下两种情况：
- dp[i - 1][0]：昨天不持股，今天什么都不做；
- dp[i - 1][1] + prices[i]：昨天持股，今天卖出股票（现金数增加）；
- dp[i][1] = Math.max(dp[i - 1][1], -prices[i])：规定了今天 持股，有以下两种情况：
- dp[i - 1][1]：昨天持股，今天什么都不做（现金数与昨天一样）；
- -prices[i]：昨天不持股，今天买入股票（注意：只允许交易一次，因此手上的现金数就是当天的股价的相反数）；
如何初始化 dp 数组：
- 第 0 天不持有：dp[0][0] = 0；
- 第 0 天持有：dp[0][1] = -prices[0]；
确定遍历顺序：从递推公式可以看出 dp[i] 都是由 dp[i - 1] 推导出来的，那么一定是从前向后遍历；
举例推导 dp 数组：以 prices = [7, 1, 5, 3, 6, 4] 为例：
索引 i = 0 索引 i = 1 索引 i = 2 索引 i = 3 索引 i = 4 索引 i = 5 dp[i][0] 规定了今天 不持股 0 0 4 4 5 5dp[i][1] 规定了今天 持股 -7 -1 -1 -1 -1 -1
复杂度
-
时间复杂度：
O(n)； -
空间复杂度：状态压缩之前是
O(n)，状态压缩后是O(1)；
代码实现
JavaScript
JavaScript
// 时间复杂度 O(n) 空间复杂度 O(n)，dp 数组第二维是常数
const maxProfit = function (prices) {
let n = prices.length;
let dp = new Array(n).fill(0).map(it => new Array(2).fill(0));
dp[0][0] = 0; // 第一天，不持有股票
dp[0][1] = -prices[0]; // 第一天，持有股票
for (let i = 1; i < n; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); // 第 i 天，不持有股票，最大值
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]); // 第 i 天，持有股票，最大值
}
return dp[n - 1][0];
};
// 状态压缩
const maxProfit = function (prices) {
let n = prices.length;
let dp = new Array(2).fill(0);
dp[0] = 0; // 第一天，不持有股票
dp[1] = -prices[0]; // 第一天，持有股票
for (let i = 1; i < n; i++) {
dp[0] = Math.max(dp[0], dp[1] + prices[i]); // 第 i 天，不持有股票，最大值
dp[1] = Math.max(dp[1], -prices[i]); // 第 i 天，持有股票，最大值
}
return dp[0];
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 337. 打家劫舍Ⅲ
上一篇
评论
