121. 買賣股票的最佳時機

題目

給定(ding)一個(ge)數組 prices ，它的(de)第 i 個(ge)元素(su) prices[i] 表示一支(zhi)給定(ding)股票第 i 天的(de)價(jia)格(ge)。

你只能選擇 某一天 買入這只股票，并選擇在 未來的某一個不同的日子 賣(mai)出(chu)該(gai)股票(piao)。設計一個算(suan)法來計算(suan)你所能獲取的最(zui)大利(li)潤。

返回你可以從(cong)這筆交易中獲(huo)取的最大利潤。如果你不能獲(huo)取任何利潤，返回 0 。

例子

輸入：[7,1,5,3,6,4]
輸出：5
解(jie)釋：在第 2 天(tian)（股票價格 = 1）的(de)時候(hou)買入，在第 5 天(tian)（股票價格 = 6）的(de)時候(hou)賣出，最大利潤 = 6-1 = 5 。

注意利潤不(bu)能是 7-1 = 6, 因(yin)為賣出(chu)價格需要(yao)大(da)于買入價格；同時，你(ni)不(bu)能在買入前賣出(chu)股(gu)票(piao)。

解法一: 暴力計算

遍歷(li)所有可能性，記錄最(zui)大值

空間復雜度：O(n)
時(shi)間復雜(za)度(du)：O(n^2)

顯然(ran)這個時間(jian)復雜度是不可接(jie)受

public int maxProfit(int[] prices) {
    if (prices == null || prices.length <= 1)
        return 0;

    int n = prices.length;
    int max = 0;
    for (int i = 0; i < n; i++) {
        for (int k = i + 1; k < n; k++) {
            int diff = prices[k] - prices[i];
            if (diff > 0 && diff > max)
                max = diff;
        }
    }
    return max;
}

解法二

股票低買高賣，

假設第一天買(mai)(mai)進，后面天數買(mai)(mai)進/賣(mai)出(chu)

1. 假設買進，價格更低，假設買進min更新當前最少值
2. 假設賣出
   1. 當前賣出利潤更大，更新最大利潤（此時最大利潤當前價格 - 之前價格最低點）
   2. 當前賣出利潤更新，則不更新

public int maxProfit(int[] prices) {
    if (prices == null || prices.length <= 1)
        return 0;


    int min = prices[0], max = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] < min) {
            min = prices[i];
        } else if (prices[i] - min > max) {
            max = prices[i] - min;
        }
    }
    return max;
}