精选力扣500题第12题 LeetCode 121. 买卖股票的最佳时机【c++详细题解】

水深无声 2021-07-24 18:01 164阅读 0赞

### 目录 ###

*   *   *  1、题目
         *  2、思路
         *  3、代码

### 1、题目 ###

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

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

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

**示例 1：**

输入：[7,1,5,3,6,4]
    输出：5
    解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
         注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

**示例 2：**

输入：prices = [7,6,4,3,1]
    输出：0
    解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

**提示：**

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

### 2、思路 ###

*  1、当枚举到`i`时，`minv`维护的是`[0,i - 1]`最小的价格，`price[i] - minv`是在当前点`i`买入的最大收益，
 *  2、计算所有点的最大收益取最大值

**时间复杂度** O(n)

### 3、代码 ###

class Solution { 
    public:
        int maxProfit(vector<int>& prices) { 
            int res = 0;
            int minv = INT_MAX;
            for(int i = 0; i < prices.size(); i++)
            { 
                minv = min(minv,prices[i]); //记录[0,i-1]股票的最小价格
                res = max(res, prices[i] - minv);
            }
            return res;
        }
    };

**原题链接:** [121. 买卖股票的最佳时机][121.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]

[121.]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/116cfd5b0ac7476fa24e78d0ca8dcf80.png