LeetCode121-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.

Example1:

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)

Example2:

Input: [7, 6, 4, 3, 1]
Output: 0

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

分析

由题意,prices数组存储了从第0天到第prices.length – 1天的股票价(当然现实中不太可能),此时如果要求只能买进一次 + 卖出一次(我个人觉得应该再加个条件,就是买家的初始资金足够多,证明每一天的股票价他都买得起),求最大利润是多少。

最初最容易想到的是求出prices中的最大值和最小值,然后做个差,便得到了最大利润…但这却是大错特错的做法,原因是:忽略了时间的流逝。如果最大值出现的日子在最小值之后,那这种方法是OK的。但若不是,比如[7, 6, 4, 3, 4, 1],如果用7 – 1 = -6明显亏本还不如4 – 3 = 1赚得多!所以这种方法是不可取的。

其实,我们可以换种角度思考这个问题:假如我们每天都要卖股票,这时候我们可以翘首回望下过去,打击下自己,哪一天买进是赚得最多的,不用说了,一定是前面天数里面price最小的那个。 那么思路就有了:只要遍历prices,边记录到今天为止的最低股票价是多少,边记录到今天为止的最大利润是多少。遍历完,答案也就有了。

代码

public class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0; //利润
        int minPrice = Integer.MAX_VALUE;
        for (int day = 0; day < prices.length; day++) {
            if(prices[day] < minPrice) minPrice = prices[day];
            int newProfit = prices[day] - minPrice;
            if (newProfit >= profit) profit = newProfit;
        }
        
        return profit;
    }
}

Leave a Comment.