LeetCode: 121. Best Time to Buy and Sell Stock

题目描述

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:
Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
Example 2:
Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

题目大意： 给定一个表示每天的股价的数组，求出只有一次买卖机会下，最大收益。

解题思路

要想在第 i 天卖出股票获得最大收益，则必须在第 i 天前股价最小的那天买入股票。 因此只需要求得第 i 天前股价的最小值，在第 i 天卖出的最大收益就是第 i 天的股价减去第 i 天前股价的最小值。最后求得使得收益最大的 i 即可。

AC 代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int frontNMinPrices = INT_MAX; // 前 i 天股价的最小值
        int profit = 0;                // 前 i 天买卖收益的最大值

        for(int i = 0; i < prices.size(); ++i)
        {
            // 计算前 i 天股价的最小值
            if(frontNMinPrices > prices[i]) frontNMinPrices = prices[i];

            // 计算第 i 天卖出收益的最大值，并判断其是不是 "前 i 天买卖收益的最大值"
            if(profit < prices[i] - frontNMinPrices)  profit = prices[i] - frontNMinPrices;
        }

        return profit;
    }
};