※ 引述《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 當最小值 然後往右找最大 : 最後在看哪個最小 : 但是有沒有更好或是更快的方法？ : 感謝 提供一個 O(n) 解法 想法： Greedy 的概念，在走訪數列 data 的過程中 假設目前找到的最佳解為 (min, max)，目前走到第 i 個元素 1. 若 data[i] > max 則可以直接更新最佳解為 (min, data[i]) 2. 若 data[i] < min 此情形能推測，若之後又出現一個更大的值 x x - data[i] > x - min 必定會成立 換句話說，用 data[i] 當 min 去往後找 一定比 用目前的 min 往後找 還更好 因此將目前的 (min, max) 列為解答候選人之一 然後改用 (data[i], data[i]) 繼續往後找 (相當於不管前面了直接從這裡開始) 3. 其他情況: 不會影響最佳解 走訪完後，檢查所有解答候選人，最佳的即為答案 實作時只要維護一個指標指向 目前最佳解的 min 然後走訪 data 時，假設當前走到的元素是 max 去更新解答 若當前元素 < 目前最佳解的 min 則更新指向 min 的指標指向當前元素 即可 這樣講實在很抽象，直接看 code data = [15, 46, 60, 23, 15, 19, 1, 22, 45, 38] p = 0 # 目前最佳解的 min 的索引值 ans = (0, 0) # (min, max) for i in range(len(data)): if data[i] < data[p]: p = i # 更新最佳解的 min 的索引值 elif data[i] - data[p] > data[ans[1]] - data[ans[0]]: ans = (p, i) # 更新解答 print('min = data[%s] = %s' % (ans[0], data[ans[0]])) print('max = data[%s] = %s' % (ans[1], data[ans[1]])) '''output min = data[0] = 15 max = data[2] = 60 ''' code 解說 & 拿範例來跑一次 初始化 p = 0 # 目前最佳解的最小值的索引值 (data[p] = 上面提到的 min) ans = (0, 0) # 記錄解答 min, max 的索引值 ---------------------------------------------------------------------- i=0 p 15, 46, 60, 23, 15, 19, 1 , 22, 45, 38 i 1. data[i] < data[p] 不成立 2. data[i] - data[p] > data[ans[1]] - data[ans[0]] 不成立 ---------------------------------------------------------------------- i=1 p 15, 46, 60, 23, 15, 19, 1 , 22, 45, 38 i 1. data[i] < data[p] 不成立 2. data[i] - data[p] > data[ans[1]] - data[ans[0]] 成立 -> 更新 ans = (0, 1) ---------------------------------------------------------------------- i=2 p 15, 46, 60, 23, 15, 19, 1 , 22, 45, 38 i 1. data[i] < data[p] 不成立 2. data[i] - data[p] > data[ans[1]] - data[ans[0]] 成立 -> 更新 ans = (0, 2) ---------------------------------------------------------------------- i=3 p 15, 46, 60, 23, 15, 19, 1 , 22, 45, 38 i 1. data[i] < data[p] 不成立 2. data[i] - data[p] > data[ans[1]] - data[ans[0]] 不成立 ---------------------------------------------------------------------- i=4 p 15, 46, 60, 23, 15, 19, 1 , 22, 45, 38 i 1. data[i] < data[p] 不成立 2. data[i] - data[p] > data[ans[1]] - data[ans[0]] 不成立 ---------------------------------------------------------------------- i=5 p 15, 46, 60, 23, 15, 19, 1 , 22, 45, 38 i 1. data[i] < data[p] 不成立 2. data[i] - data[p] > data[ans[1]] - data[ans[0]] 不成立 ---------------------------------------------------------------------- i=6 p 15, 46, 60, 23, 15, 19, 1 , 22, 45, 38 i 1. data[i] < data[p] 成立 -> 之後若出現一個大數字 x 則 x - data[i] > x - data[p] 必成立 因此更新 p = i = 6 2. data[i] - data[p] > data[ans[1]] - data[ans[0]] 不成立 ---------------------------------------------------------------------- i=7 p 15, 46, 60, 23, 15, 19, 1 , 22, 45, 38 i 1. data[i] < data[p] 不成立 2. data[i] - data[p] > data[ans[1]] - data[ans[0]] 不成立 好啦後面都是不成立就不再浪費篇輻了XD 最後取出 ans 即為找到的 min, max -- 光明 的背後 是 黑暗 黑暗 的背後 還是 黑暗 由此可知 黑暗 > 光明 Q.E.D. --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.235.135 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/Python/M.1439833943.A.26E.html