題目
難度：★☆☆☆☆
類型：數(shù)組
給定一個(gè)數(shù)組，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格蚜枢。
如果你最多只允許完成一筆交易（即買入和賣出一支股票）径荔，設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤(rùn)休讳。
注意你不能在買入股票前賣出股票主届。
示例
示例 1:
輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買入膀篮，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出，最大利潤(rùn) = 6-1 = 5 岂膳。
注意利潤(rùn)不能是 7-1 = 6, 因?yàn)橘u出價(jià)格需要大于買入價(jià)格。
示例 2:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤(rùn)為 0磅网。
解答
股票利潤(rùn)是賣出時(shí)間t2時(shí)的價(jià)格與買入時(shí)間t1時(shí)的價(jià)格之差谈截，這里有t2>t1存在，為了獲得最大利潤(rùn)涧偷，賣出時(shí)的價(jià)格與買入時(shí)價(jià)格的差值最大簸喂，我們可以考慮使用暴力求解法尋找所有的買入、賣出價(jià)格對(duì)燎潮，計(jì)算利潤(rùn)并更新利潤(rùn)最大值喻鳄，但是計(jì)算復(fù)雜度較高，這里不再贅述确封。
我們使用一次遍歷方法除呵，用變量（cur_max_profit）和（cur_min）表示遍歷到當(dāng)前位置為止出現(xiàn)過的最大利潤(rùn)和當(dāng)前的最小價(jià)格，在每次遍歷時(shí)爪喘，如果遇到更小的股票價(jià)格颜曾，則更新cur_min，當(dāng)前利潤(rùn)的計(jì)算方式是當(dāng)前價(jià)格與cur_min之間的差值秉剑，如果遇到更大當(dāng)前利潤(rùn)泛豪，則更新變量cur_max_profit，最終返回cur_max_profit即可侦鹏。
class Solution:
def maxProfit(self, prices):
if not prices: # 輸入為空
return 0 # 返回零
cur_max_profit, cur_min = 0, prices[0] # 初始化記錄中最高利潤(rùn)和記錄中最小價(jià)格
for i in range(len(prices)-1): # 進(jìn)行迭代
if prices[i] < cur_min: # 如果當(dāng)前價(jià)格小于記錄中最小價(jià)格
cur_min = prices[i] # 更新記錄中最小價(jià)格
cur_profit = prices[i+1] - cur_min # 當(dāng)前利潤(rùn)=當(dāng)前價(jià)格-記錄中最小價(jià)格
if cur_profit > cur_max_profit: # 如果當(dāng)前利潤(rùn)大于記錄中最高利潤(rùn)
cur_max_profit = cur_profit # 更新記錄中最高利潤(rùn)
return cur_max_profit # 返回最高利潤(rùn)
如有疑問或建議诡曙，歡迎評(píng)論區(qū)留言~
