swift算法：買賣股票的最佳時機

1、描述

給定一個數組，它的第i個元素是一支給定股票第i天的價格。

如果你最多隻允許完成一筆交易（即買入和賣出一支股票），設計一個算法來計算你所能擷取的最大利潤。

注意你不能在買入股票前賣出股票。

例1：輸入：[7, 1, 5, 3, 6, 4]

          輸出：5

          解釋：在第二天（股票價格=1）的時候買入，在第五天（股票價格=6）的時候賣出，最大利潤 = 6 - 1 = 5。

                      注意利潤不能是7-1=6，因為賣出價格需要大于買入價格

例2：輸入：[7, 6, 4, 3, 1]

          輸出：0

          解釋：在這種情況下，沒有交易完成，是以雖大利潤為0

2、算法

1)暴力法

思想：我們需要找出給定數組中兩個數字之間的最大內插補點（即，最大利潤）。此外，第二個數字（賣出價格）必須大于第一個數字（買入價格）。

         形式上，對于每組i 和j（其中j>i）我們需要找出max(prices[j]−prices[i])。

時間複雜度：O(n^2)

func maxProfit(_ prices: [Int]) -> Int {
        /*
         暴力法：
         */
        if prices.count==0 || prices.count==1{
            return 0
        }
        var maxprofit : Int = 0
        for i in 0..<prices.count-1 {
            for j in (i+1)..<prices.count{
                let profit = prices[j]-prices[i]
                if profit > maxprofit {
                    maxprofit = profit
                }
            }
        }
        return maxprofit
    }           

2）一次周遊

解法一：

思想： 需要找到最小的谷之後的最大的峰。 我們可以維持兩個變量——minprice 和 maxprofit，它們分别對應迄今為止所得到的最小的谷值和最大的利潤（賣出價格與最低價格之間的最大內插補點）。

時間複雜度：O(n)

func maxProfit(_ prices: [Int]) -> Int {
        /*
         一次周遊：
         */
        var minprice = Int.max
        var maxprofit : Int = 0
        for i in 0..<prices.count {
            if prices[i] < minprice{
                minprice = prices[i]
            }else if prices[i] - minprice > maxprofit{
                maxprofit = prices[i]-minprice
            }
        }
        return maxprofit
    }
               

解法二：

思想：一次周遊， 直接把最小值放在數組的第一位

func maxProfit(_ prices: [Int]) -> Int {
        /*
         一次周遊：
         */
        if prices.count==0 || prices.count==1{
            return 0
        }
        var minprice = prices[0]
        var maxprofit : Int = 0
        for i in 1..<prices.count {
            if prices[i] > minprice{
                maxprofit = prices[i]-minprice > maxprofit ? prices[i]-minprice : maxprofit
            }else{
                minprice = prices[i]
            }
        }
        return maxprofit
    }           

3）快排

func maxProfit(_ prices: [Int]) -> Int {
        /*
         快排思想：
         */
        if prices.count==0 || prices.count==1{
            return 0
        }
        var maxprofit : Int = 0
        var minIndex = 0
        var maxIndex = 0
        for i in 1..<prices.count {
            if prices[i] < prices[minIndex] {
                maxIndex = i
                minIndex = i
            }else if prices[i] > prices[maxIndex]{
                maxIndex = i
                maxprofit = max(maxprofit, prices[maxIndex]-prices[minIndex])
            }
        }
        return maxprofit
    }