LeetCode - 121 买卖股票的最佳时机

目录

题目来源

题目描述

示例

提示

题目解析

算法源码

题目来源

121. 买卖股票的最佳时机 - 力扣（LeetCode）

题目描述

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例

提示

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

题目解析

本题其实可以用滑动窗口的思维去思考，

我们用一个指针 i 遍历prices数组（for循环），如果i指针指向的prices元素是0~i范围内最小值，则作为滑动窗口左边界，然后i指针继续向右遍历，

• 如果没有遇到比滑动窗口左边界更小的元素，则都当成滑动窗口右边界的值，因此我们统计出每个右边界与左边界的插值diff，并只保留最大的diff。
• 如果遇到了比滑动窗口左边界更小的元素，则更新滑动窗口的左边界，然后继续前面逻辑

 下面算法代码中，min值就是滑动窗口左边界的值，每一个prices[i]都可以当成滑动窗口右边界的值，diff是滑动窗口右边界和左边界的插值，我们只保留最大的diff作为题解。

算法源码

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let min = prices[0]
    let diff = 0

    for(let i=1; i<prices.length; i++) {
        if(prices[i] < min) {
            min = prices[i]
        } else {
            diff = Math.max(diff, prices[i]-min)
        }
    }

    return diff
};