C语言重构【121】买卖股票的最佳时机

末蓝、 2022-12-08 15:31 138阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

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

#### 方案： ####

*  贪心/动态规划

#include <iostream>
    #include <vector>
    #include <math.h>
    
    using namespace ::std;
    class Solution
    { 
    public:
        int maxProfit(vector<int> &prices)
        { 
            if (prices.size() == 0)
                return 0;
            int pro = 0;
            int buy = prices[0];
            for (int i = 1; i < prices.size(); i++)
            { 
                //这种情况是倒数
                pro = max(prices[i] - buy, pro);
                if (buy > prices[i])
                    buy = prices[i];
            }
            return pro;
        }
    };

##### 复杂度计算 #####

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

[Git]: https://github.com/ch98road/leetcode