精选50题之 121. 买卖股票的最佳时机

清疚 2024-04-19 11:55 46阅读 0赞

### 腾讯精选练习（50 题）之 121. 买卖股票的最佳时机 ###

*   *  原题目链接
     *  直接实现
     *  其它方式

## [原题目链接][Link 1] ##

给定一个数组，它的第 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。

## 直接实现 ##

由于只能进行一次交易，实际上就是低买高卖。  
所以就是顺序查找，标注最小值，并用其他点和它做差，为临时差值。返回差值最大值。

class Solution {
        
    public:
        int maxProfit(vector<int>& prices) {
        
            int max_profit = 0;
            int min_paid = INT_MAX;
            for (int i = 0; i < prices.size(); i++) {
        
                min_paid = min(min_paid, prices[i]);
                max_profit = max(max_profit, prices[i] - min_paid);
            }
            return max_profit;
        }
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]  
复杂度分析：

*  时间复杂度：O(N)
 *  空间复杂度：O(1)

## 其它方式 ##

看了一下，各种解法五花八门。  
但是有一篇写动态规划延伸的DP table（状态机？）的题解很不错，贴在下面。  
[labuladong 的回答][labuladong] 十分酣畅，一下没看懂?留着学习。

[Link 1]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/c190bc6dd6484f6a8d3cf0d56a09f299.png
[labuladong]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-l-3/