#55317: 關於O(N)


Ixcy (Ixcy)


雖然N <= 100,可以直接O(N^2)比對就好,但你既然點進來了大概不是要看這個的

不妨假設我們必須要在某一天賣出,也就是固定一個變數(比如sellday)

那麼,我們必須要在sellday前挑選某一天買入,而我們當然會想要挑選最便宜的那一天(這樣子利潤最大)

由上,藉由一個迴圈,我們可以嘗試每一個可能的sellday

因為買入一定在賣出之前,每一個sellday你都可以記錄它之前最便宜的價格

如果沒有sellday成立,輸出-1

同樣地,如果今天是期貨(futures),我們依舊可以由從後方遍歷的方式進行時間O(N)查找,但空間O(N)就不可避了