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

難度：簡單
題目描述：給定一個數組 prices 幔翰，它的第 i 個元素 prices[i] 表示一支給定股票第 i 天的價格。
你只能選擇 某一天 買入這只股票米绕，并選擇在 未來的某一個不同的日子 賣出該股票致份。設計一個算法來計算你所能獲取的最大利潤哟冬。
返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤，返回 0 识椰。

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

分析

本題為求股票買入賣出之間的最大利潤入愧，實際上是求數組中最大數和最小數的差值問題鄙漏， 
但是股票的買賣存在這先買后賣的順序性嗤谚，故尋找數組中最大數和最小數則為相對于位置來說的 
例如數組[7,1,5,3,6,4]中，最小值為1怔蚌，最大值為7巩步，但是不存在先賣后買的情況，所以只能尋找最小值1后面的最大值6桦踊，故差值為5椅野，即利潤為5 
清楚了題目要求后就變得簡單了很多，可以使用雙指針的方法籍胯，一個指針為buy竟闪，指向買股票時的價格，另一個指針為sale芒炼，指向賣股票時的價格 
profit = sale - buy 
這時就可以遍歷數組瘫怜，通過遍歷尋找買股票的最低點和賣股票的最高點。 
由于1 <= prices.length <= 105 所以對于buy和sale取值之前需要判斷數組長度本刽，如果數組長度為1鲸湃，則直接返回0。 
并且此方法還有一種情況子寓，即數組就兩個元素暗挑，例如：[7,1] 
這種情況下profit初始化為-6，不符合題目標準斜友，所以在返回值處需要進行判斷 

優(yōu)化： 
本題實質上不需要考慮sale值的存儲炸裆，因為sale值可以通過遍歷數組得到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;
        }
    }