※ 引述《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/cn.aspx?n=bbs/Python/M.1439833943.A.26E.html