Best Time to Buy and Sell Stock

「爱情、让人受尽委屈。」 2022-05-08 07:10 247阅读 0赞

*  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 (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: \[7,1,5,3,6,4\]  
Output: 5  
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 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  
Explanation: In this case, no transaction is done, i.e. max profit = 0.

*  最佳解答

So we maintain a variable curMin to represents currently the minimun price in [0, j).
    The max profit for selling it on day j is prices[j] - curMin.

public int maxProfit(int[] prices) {
            if (prices == null || prices.length <= 1) {
                return 0;
            }
            
            int max = 0;
            int curMin = prices[0];
            int i = 0;
            int j = 1;
            while (j < prices.length) {
                curMin = Math.min(prices[i], curMin);
                max = Math.max(max, prices[j] - curMin);
                j++;
                i++;
            }
            return max;
        }

发表评论取消回复

表情：

评论列表（有 0 条评论，247人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 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 d

╰+哭是因爲堅強的太久メ/ 2022年08月08日 12:57/ 0 赞/ 117 阅读

相关 Leetcode: 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 d

电玩女神/ 2022年08月07日 12:34/ 0 赞/ 37 阅读

相关 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.

冷不防/ 2022年07月15日 01:20/ 0 赞/ 243 阅读

相关 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.

梦里梦外;/ 2022年07月15日 01:20/ 0 赞/ 238 阅读

相关 [Leetcode] 121. Best Time to Buy and Sell Stock

121. Best Time to Buy and Sell Stock Say you have an array for which the i-th element

傷城~/ 2022年06月13日 23:53/ 0 赞/ 277 阅读

相关 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 da

不念不忘少年蓝@/ 2022年06月10日 14:10/ 0 赞/ 272 阅读

相关 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.

た入场券/ 2022年05月16日 14:11/ 0 赞/ 232 阅读

相关 Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock Say you have an array for which the ith element is

「爱情、让人受尽委屈。」/ 2022年05月08日 07:10/ 0 赞/ 248 阅读

相关 Best Time to Buy and Sell Stock II

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

刺骨的言语ヽ痛彻心扉/ 2022年01月07日 10:03/ 0 赞/ 266 阅读

相关 best-time-to-buy-and-sell-stock

/\\ \ \ @author gentleKay \ Say you have an array for which the i th element is th

客官°小女子只卖身不卖艺/ 2021年11月09日 08:34/ 0 赞/ 273 阅读