121. 買賣股票的最佳時(shí)機(jī) - 力扣（LeetCode） (leetcode-cn.com)

難度：簡單
題目描述：給定一個(gè)數(shù)組 prices ，它的第 i 個(gè)元素 prices[i] 表示一支給定股票第 i 天的價(jià)格。
你只能選擇 某一天 買入這只股票，并選擇在 未來的某一個(gè)不同的日子 賣出該股票。設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤。
返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤，返回 0 。

類型一樣的題
股票問題系列通解（轉(zhuǎn)載翻譯） - 力扣（LeetCode） (leetcode-cn.com)

分析

本題為求股票買入賣出之間的最大利潤，實(shí)際上是求數(shù)組中最大數(shù)和最小數(shù)的差值問題， 
但是股票的買賣存在這先買后賣的順序性，故尋找數(shù)組中最大數(shù)和最小數(shù)則為相對于位置來說的 
例如數(shù)組[7,1,5,3,6,4]中，最小值為1，最大值為7，但是不存在先賣后買的情況，所以只能尋找最小值1后面的最大值6，故差值為5，即利潤為5 
清楚了題目要求后就變得簡單了很多，可以使用雙指針的方法，一個(gè)指針為buy，指向買股票時(shí)的價(jià)格，另一個(gè)指針為sale，指向賣股票時(shí)的價(jià)格 
profit = sale - buy 
這時(shí)就可以遍歷數(shù)組，通過遍歷尋找買股票的最低點(diǎn)和賣股票的最高點(diǎn)。 
由于1 <= prices.length <= 105 所以對于buy和sale取值之前需要判斷數(shù)組長度，如果數(shù)組長度為1，則直接返回0。 
并且此方法還有一種情況，即數(shù)組就兩個(gè)元素，例如：[7,1] 
這種情況下profit初始化為-6，不符合題目標(biāo)準(zhǔn)，所以在返回值處需要進(jìn)行判斷 

優(yōu)化： 
本題實(shí)質(zhì)上不需要考慮sale值的存儲，因?yàn)閟ale值可以通過遍歷數(shù)組得到prices[i]， 
而且profit值的變更也可以不考慮sale值

解題

優(yōu)化前

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length < 2){
                return 0;
            }
        int buy = prices[0];
        int sale = prices[1];
        int profit = sale - buy;
        for (int i = 1; i < prices.length - 1; i++) {
            if (prices[i] < buy) {
                buy = prices[i];
            }
            if (prices[i + 1] - buy > profit) {
                sale = prices[i + 1];
                profit = sale - buy;
            }
        }
        return profit > 0 ? profit : 0;
    }
}

優(yōu)化后

class Solution {
        public int maxProfit(int[] prices) {
            int buy = prices[0];
            int profit = 0;
            for (int i = 1; i < prices.length; i++) {
                if (prices[i] - buy > profit) {
                    profit = prices[i] - buy;
                }
                buy = prices[i] < buy ? prices[i] : buy;
            }

            return profit;
        }
    }