作者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/cn.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