【算法题】买卖股票的最好时机(一)

买卖股票的题大概有 6 道，可以使用动态规划全部解决，但这题是最简单的一道，如果使用动态规划，有点杀鸡用牛刀了，没必要。

这题说的是只能交易一次，求所获得的最大利润，也就是在最低价的时候买入，在后面最高价的时候卖出，我们可以使用一个变量 minV 来记录前面遍历过的最小值，这个最小值不是固定的，也是会跟着变动的，然后用数组后面的值减去这个最小值差，这个差就是利润，我们只需要保存最大利润即可。

    public int maxProfit(int[] prices) {
        int minV = prices[0];// 遍历过的最小值
        int ans = 0;
        for (int price : prices) {
            minV = Math.min(minV, price);// 记录最小值
            ans = Math.max(ans, price - minV);// 记录差值的最大值
        }
        return ans;
    }

public:
    int maxProfit(vector<int> &prices) {
        int minV = prices[0];// 遍历过的最小值
        int ans = 0;
        for (int price: prices) {
            minV = min(minV, price);// 记录最小值
            ans = max(ans, price - minV);// 记录差值的最大值
        }
        return ans;
    }

各大厂算法面试题已经整理好了，请看这里：《算法专栏》