交易模擬題 最佳股票買賣I Best Time to Buy and Sell Stock_Leetcode#121

這題的題目在這裡:

題目敘述

題目會給我們一個陣列prices，裡面的數值代表每一個交易日的股票股價。

題目給我們一次做多的機會，也就是A交易日買進，B交易日賣出，請問最大獲利是多少？(此處不需要考慮現實面的交易稅、手續費...等因素)

如果無法獲利，則題目要求return 0。

測試範例

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

約束條件

Constraints:

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^5

演算法

這邊有一個常見的盲點，一開始看完題目的同學，可能有一種想法，一次做多的最大獲利，就找出股價的最高點和最低點，兩者做相減。

這乍看很有道理，但是這個最高點和最低點實際上是錯的，為什麼?

這是因為，已經先入為主，預設最終股價會上漲，但是，其實這個假設並不是永遠成立，而且題目的敘述也 沒有 給予最終股價會上漲的保證。

假如，遇到如下圖的股價走勢時，最高點和最低點這個算法就遇到矛盾了。實際情況是，做多根本無法獲利，應該回傳0。

在這裡，提供一個正確的演算法，首先，先建立兩個變數如下所述:

cur_lowest_buy_price 代表截至目前為止，已知的股票的最低(買進)價格，初始化為正無窮大。

cur_profit 代表截至目前為止，一次做多可以獲利的最大值，初始化為0。

接著，建立一個線性掃描迴圈，從第一個交易日掃描到最後一個交易日，紀錄股票的最低(買進)價格 cur_lowest_buy_price。

同時，檢查當天股價 - 已知的股票的最低(買進)價格是否能產生獲利，如果可以，就比較大小並且更新到最大獲利cur_profit裡面。

最終，cur_profit就是一次做多可以獲利的最大值。

程式碼

class Solution:
　def maxProfit(self, prices: List[int]) -> int:
　　

　　# 1. lowest buy in price so far
　　# 2. best profit with single pair of trade so far
　　cur_lowest_buy_price, cur_profit = float('inf'), 0
　　
　　
　　for stock_price in prices:
　　　
　　　prev_lowest_buy_pirce, prev_profit = cur_lowest_buy_price, cur_profit
　　　
　　　# update lowest buy-in price so far
　　　cur_lowest_buy_price = min(prev_lowest_buy_pirce, stock_price)
　　　
　　　# update best profit we can reach by single pair of trade so far
　　　cur_profit = max(prev_profit, stock_price - prev_lowest_buy_pirce  )
　　　
　　　
　　return cur_profit

複雜度分析

時間複雜度:

O( n ) 一個線性掃描，長度和原本的股價陣列一樣長。

空間複雜度:

O(1)　使用到的都是固定尺寸的臨時變數，為常數級別。

等價的Top-down DP 由上而下的動態規劃 寫法:

class Solution:
　def maxProfit(self, prices: List[int]) -> int:
　　
　　
　　def trade(day_d):
　　　
　　　if day_d == 0:
　　　　
　　　　# Initialization on day_#0
　　　　lowest_buy_in_price, max_profit = prices[0], 0
　　　　return (lowest_buy_in_price, max_profit)
　　　
　　　prev_lowest_price, prev_max_profit = trade( day_d-1 )
　　　
　　　# update lowest buy-in price so far
　　　cur_lowest_price = min(prev_lowest_price, prices[day_d])
　　　
　　　# update max profit so far
　　　cur_max_profit = max(prev_max_profit, prices[day_d] - prev_lowest_price)
　　　
　　　return cur_lowest_price, cur_max_profit
　　
　　#-------------------------------------------------
　　last_day = len(prices)-1
　　return trade(last_day)[1]

複雜度分析

時間複雜度:

O( n ) 從最後一個交易日 回溯到第一個交易日，長度和原本的股價陣列一樣長。

空間複雜度:

O(n)　DP遞迴計算深度就是全部的交一日天數，長度和原本的股價陣列一樣長。

關鍵知識點

理解 最高點和最低點相減 這種錯誤演算法的盲點和矛盾之處。

正確的演算法應該找出，在此之前，最低的股票買進價格，和當日可賣出的股價相比較，中間產生的價差，才是一次最多可以得到的最大獲利。

Reference:

[1] Python/Go/JS/C++ O(n) by DP [w/ Visualization] - Best Time to Buy and Sell Stock - LeetCode