Re: [問題] 如何在數列中找到max min且max在min右邊
其實這個和 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 好幾條街了...
--
→
08/10 00:59,
08/10 00:59
→
08/10 02:16,
08/10 02:16
→
08/10 20:18,
08/10 20:18
→
08/10 20:19,
08/10 20:19
→
08/10 20:21,
08/10 20:21
→
08/11 20:23,
08/11 20:23
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.161.94.175
※ 文章網址: https://www.ptt.cc/bbs/Python/M.1439829770.A.D5C.html
※ 編輯: uranusjr (218.161.94.175), 08/18/2015 00:44:18
推
08/30 10:09, , 1F
08/30 10:09, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 3 篇)：
Python 近期熱門文章
PTT數位生活區 即時熱門文章
