121.买卖股票的最佳时机

链接：121.买卖股票的最佳时机
难度：Easy
标签：数组、动态规划
简介：给定一个数组 prices ，它的第  i 个元素  prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

题解 1 - cpp

• 编辑时间：2022-03-14
• 执行用时：100ms
• 内存消耗：91MB
• 编程语言：cpp
• 解法介绍：考虑到只能交易一次，每遍历到一个值与前面的最小值进行比较。

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

题解 2 - python

• 编辑时间：2023-10-01
• 执行用时：224ms
• 内存消耗：25.9MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
            def maxProfit(self, prices: List[int]) -> int:
                prev = prices[0]
                res = 0
                for i in range(1, len(prices)):
                    res = max(res, prices[i] - prev)
                    prev = min(prev, prices[i])
                return res