买卖股票的最佳时机-121
sl1673495 opened this issue · 0 comments
sl1673495 commented
给定一个数组,它的第 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。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
循环版
暴力循环,i 为卖出的天数,j 为买入的天数。
i 从 1 开始,因为第 0 天不可能卖出。
j 从 0 开始到 i 结束,因为买入的天数一定小于卖出的天数。
然后在这两者间的差价中找最大值。
题解
/**
* 循环版
* @param {number[]} prices
* @return {number}
*/
let maxProfit = function (prices) {
let max = 0;
for (let i = 1; i < prices.length; i++) {
for (let j = 0; j < i; j++) {
let price = prices[j];
let sale = prices[i] - price;
max = Math.max(max, sale);
}
}
return max;
};
动态规划版
思路
状态转移方程是
当天的最大收益 = max(
当天卖出:当天的价格 - 过去几天最低的价格,
当天不卖:过去几天的最大收益
)
题解
/**
* DP版
*/
let maxProfit = function (prices) {
let n = prices.length;
if (!n || n === 1) return 0;
// 最大收益
let prevMax = 0;
// 最小价格
let prevMin = prices[0];
for (let i = 1; i < n; i++) {
let price = prices[i];
prevMax = Math.max(price - prevMin, prevMax);
prevMin = Math.min(price, prevMin);
}
return prevMax;
};