当前位置：首页 > article >正文

买卖股票的最佳时机（js实现，LeetCode：121）

article 2025/3/26 0:40:45

看到这道题我的第一想法是使用双指针暴力破解

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
    let fast = 1
    let slow = 0
    let payoffs = 0
    while (slow < prices.length - 1) {
        payoffs = Math.max(payoffs, prices[fast] - prices[slow])
        fast += 1
        if (fast > prices.length - 1) {
            slow += 1
            fast = slow + 1
        }
    }
    return payoffs
};

但是很可惜,遇到了这么个测试用例

这里想到了贪心算法，只走一次遍历，空间复杂度为O(1)

/**
 * @param {number[]} prices
 * @return {number}
 */
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;
};

查看全文

http://www.kler.cn/a/600254.html