买卖股票的最佳时机

一 问题描述

给定一个数组，找到两个元素，使得后一个元素减去前一个元素的值最大，返回这个最大值。如果不存在则返回0。

121.买卖股票的最佳时机

二 解决方法

1 暴力法

分析

因为需要找到两个元素，很容易想到遍历两次数组的暴力法：第一层循环记录前一个元素下标，第二层循环记录后一个元素下标，找到二者差的最大值。

代码

• 第一次遍历数组，用 i 记录前一个元素下标

• 第二次遍历数组，用 j 记录后一个元素下标，且 j 直接从 i + 1 开始

• 二者相减，保存相减后的最大值

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int nums = prices.size();							// 数组长度
        int ret = 0, cur;									// 返回值（最大差值）和临时值
        for (int i = 0; i < nums - 1; ++i) {				// 第一层循环：记录前一个元素下标
            for (int j = i + 1; j < nums; ++j) {			// 第二层循环：记录后一个元素下标
                cur = prices[j] - prices[i];				// 计算二者差值
                if (cur > ret)	{							// 与最大差值比较
                		ret = cur;							// 更新最大差值
                }
            }
        }
        return ret;											// 返回结果
    }
};

这里运用到了一个代码小技巧，因为最小值必为0（自己减自己），因此可令返回值默认为0，之后就可在两层循环中省去下标重复的地方。比如： i < nums - 1 和 j = i + 1 。

2 维护最小值

分析

对于数组里任一元素来说，要想取得最大结果差值，其必须和出现在数组前面的最小值相减。因此可以维护一个最小值，用于跟当前数组元素比较。此时只用了一个循环。

代码

• 记录首值为最小值，记录0为最大差值

• 遍历数组除首值之外部分

• 更新最大差值，更新最小值

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int nums = prices.size();								// 数组长度
        int minPrice = prices[0], maxProfit = 0;				// 最小值，最大差值
        for (int i = 1; i < nums; ++i) {						// 遍历数组
            maxProfit = max(maxProfit, prices[i] - minPrice);	// 更新最大差值
            minPrice = min(prices[i], msnPrice);				// 更新最小值
        }
        return maxProfit;										// 返回结果值
    }
};

三 总结

1. 暴力法用了两层循环，所以时间复杂度为 $0(n^2)$ ；只用了常数个变量，所以空间复杂度为 $0(1)$ 。因为时间复杂度高，无法通过时间限制测试。

2. 维护最小值法只用了单层循环，时间复杂度为 $0(n)$ ；只用了常数个变量，所以空间复杂度也为 $0(1)$ 。

3. 维护最小值也可以看作双指针法的变体，其中仍有一个指针用于遍历数组，但另一个记录下标的指针则变成了记录元素值的变量。