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

小灰灰 2023-09-23 17:05 113阅读 0赞

**目录**

题目来源

题目描述

示例

提示

题目解析

算法源码

--------------------

### 题目来源 ###

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

### 题目描述 ###

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

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

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

### 示例 ###

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:59px;">输入</td> 
   <td style="width:439px;">[7,1,5,3,6,4]</td> 
  </tr> 
  <tr> 
   <td style="width:59px;">输出</td> 
   <td style="width:439px;">5</td> 
  </tr> 
  <tr> 
   <td style="width:59px;">说明</td> 
   <td style="width:439px;"> <p>在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。</p> <p>注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。</p> </td> 
  </tr> 
 </tbody> 
</table>

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>输入</td> 
   <td>prices = [7,6,4,3,1]</td> 
  </tr> 
  <tr> 
   <td>输出</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>说明</td> 
   <td>在这种情况下, 没有交易完成, 所以最大利润为 0。</td> 
  </tr> 
 </tbody> 
</table>

### 提示 ###

*  `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
    };

![21c2881095464903b01c239d7e37f11d.png][]

[121. _ - _LeetCode]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
[21c2881095464903b01c239d7e37f11d.png]: https://img-blog.csdnimg.cn/21c2881095464903b01c239d7e37f11d.png