作者uranusjr (←这人是超级笨蛋)
看板Python
标题Re: [问题] 如何在数列中找到max min且max在min右边
时间Tue Aug 18 00:42:47 2015
其实这个和 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 好几条街了...
--
1F：→ GNUGCC:void main(void) 的写法是可行的唷^^08/10 00:59
2F：→ GNUGCC:虽然这个写法较传统,但是语法与文法都正确哦^^08/10 02:16
3F：→ GNUGCC:目前我使用的 Visual C++ 都接受 void main(void) 与 08/10 20:18
4F：→ GNUGCC:int main(void),各位可以把 C++ 专案改成原生 C++ 类型来 08/10 20:19
5F：→ GNUGCC:用 void main(void) 来写发现也可通过编译. 08/10 20:21
6F：→ GNUGCC:这个就是 Visual C++ 的弹性.08/11 20:23
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 218.161.94.175
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Python/M.1439829770.A.D5C.html
※ 编辑: uranusjr (218.161.94.175), 08/18/2015 00:44:18
7F：推 dk1986: 发现野生的TP ! 08/30 10:09