作者joe1234wu ()
看板Python
標題[問題] 如何在數列中找到max min且max在min右邊
時間Mon Aug 17 23:24:32 2015
想請教大家....
最近遇到一個問題
情境會變成
有個數列
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 當最小值 然後往右找最大
最後在看哪個最小
但是有沒有更好或是更快的方法？
感謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.228.106.198
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Python/M.1439825075.A.20F.html
1F：推 ckc1ark: 掃一遍記錄目前看過的最小值 再和目前的值相減找最大? 08/17 23:33
2F：→ ckc1ark: 你的目標應該是找ai和aj (j>i)然後maximize(aj-ai)吧 和m 08/17 23:35
3F：→ ckc1ark: ax min有關係嗎 08/17 23:35
4F：→ joe1234wu: 對 樓上的敘述比較對 但是無法照你第一樓說的方法做 08/17 23:37
5F：推 ckc1ark: 我指的是每看一個值就當aj, ai當然不意外是已經看過的(a1 08/17 23:40
6F：→ ckc1ark: ~j-1)最小值 08/17 23:40
7F：→ joe1234wu: 你這個方法跟我一開始想的一樣 只是在想有沒有辦法更快 08/17 23:56
8F：→ joe1234wu: 掃完一次 O(n) 就找完 08/17 23:56
9F：推 ckc1ark: 最小值更新每次O(1)*看完每個值是O(n)沒錯啊 我有誤會什 08/18 00:02
10F：→ ckc1ark: 麼嗎 08/18 00:03
11F：推 Thisisnotptt: 樓上的做法感覺應該沒錯，差的n-Order應該是差再一 08/18 00:37
12F：→ Thisisnotptt: 個是直接記錄下最大值，每往前走便比較一次是否大 08/18 00:37
13F：→ Thisisnotptt: 於最大值，若非則不處理，若是則更新最大值，所以 08/18 00:38
14F：→ Thisisnotptt: 整個只走過一次，並不用每走一步就再用一個迴圈去 08/18 00:38
15F：→ Thisisnotptt: 找一次最大值 08/18 00:38
16F：→ joe1234wu: 感謝詳細解釋 那0~j-1但最小值該如何更新呢？ 08/18 00:51