作者uranusjr (←這人是超級笨蛋)
看板Python
標題Re: [問題] 如何在數列中找到max min且max在min右邊
時間Tue Aug 18 00:42:47 2015
其實這個和 Python 沒太大關係, 發到解題板之類的可能更好
不過簡單的做法大概是這樣
※ 引述《joe1234wu ()》之銘言：
: 想請教大家....
: 最近遇到一個問題
: 情境會變成
: 有個數列
: ex: [15, 46, 60, 23, 15, 19, 1, 22, 45, 38]
: 我要如何找到 Max and min 使得 Max-min 最大
: 但是 Max 必須在min 的右邊
: 以上面的例子為例
: 就是 Max = 60 min = 15( 因為 60-15 = 45會是最大)
: 我有想過 O(n^2)的方式 就是每次index 當最小值 然後往右找最大
: 最後在看哪個最小
要掃一次 list 基本是無法避免
所以重點就是決定每個 index 的最小值後不要再回頭找最大值
而是要記住之前找過的最大值重複利用
這樣就可以 O(n)
: 但是有沒有更好或是更快的方法？
: 感謝
其實你的最小值從後面掃回來會比較好想：
有 [38, 45, 22, 1, 19, 15, 23, 60, 46, 15]
要找到 max 在 min 的「左邊」（前面）
這樣你就會發現其實你一直在掃重複的東西
重點是, 當你往前找下一個最小值時
下一個最小值可以用的可能最大值一定是 max(前一個最大值, 前一個最小值)
例如上面第三項是 22, 可以用來比的是 38, 45, 所以最大值是 45
第四項是 1, 可以來比的就是上面那兩個與第三項, 所以最大值是 max(45, 22) = 45
所以你只要記住迴圈上一輪找到的最大最小值, 就可以不用一直往前重掃
(故意不放程式, 自己想吧)
====
But, 人生就是這個 but
上面那個方法基本上要用 Python 的 for 實作
如果你的 list 不長, 說不定這樣還比較快...
max(
max(b - a for b in numbers[i:] or [float('-inf')])
for i, a in enumerate(numbers)
)
這基本上就是你一開始的 O(n^2) 暴力法
但因為 max 用的是 C 的 for 迴圈, 直接就打趴 Python 好幾條街了...
--
1F：→ GNUGCC:void main(void) 的寫法是可行的唷^^08/10 00:59
2F：→ GNUGCC:雖然這個寫法較傳統,但是語法與文法都正確哦^^08/10 02:16
3F：→ GNUGCC:目前我使用的 Visual C++ 都接受 void main(void) 與 08/10 20:18
4F：→ GNUGCC:int main(void),各位可以把 C++ 專案改成原生 C++ 類型來 08/10 20:19
5F：→ GNUGCC:用 void main(void) 來寫發現也可通過編譯. 08/10 20:21
6F：→ GNUGCC:這個就是 Visual C++ 的彈性.08/11 20:23
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.161.94.175
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Python/M.1439829770.A.D5C.html
※ 編輯: uranusjr (218.161.94.175), 08/18/2015 00:44:18
7F：推 dk1986: 發現野生的TP ! 08/30 10:09