z*********8
发帖数: 2070 | 1 给一个股票在每分钟的价格， 要求设计数据结构/算法使得可以在最短时间内得到这个
股票在时间区间【t1, t2】内的最高最低价格 |
t****d
发帖数: 423 | 2 最大值出现在t1, t2, 和t1 t2之间的波峰
所以是不是可以用一个数据结构存储所有的波峰
同理也可以用一个数据结构存储所有的波谷
至于数据机构，可以用hashMap，时间戳为key
【在 z*********8 的大作中提到】
: 给一个股票在每分钟的价格， 要求设计数据结构/算法使得可以在最短时间内得到这个
: 股票在时间区间【t1, t2】内的最高最低价格
|
p*****2
发帖数: 21240 | 3 这是什么公司的题？有点黑呀。最简单的就是用DP了。 |
r*********n
发帖数: 4553 | |
p*****2
发帖数: 21240 | 5
是。O(n), O(1)的好写吗？
【在 r*********n 的大作中提到】
: 这是Range Minimum Query吧
: http://en.wikipedia.org/wiki/Range_Minimum_Query#CITEREFFischer
|
r**h
发帖数: 1288 | 6 我觉得这题的考点是large scale情况下的处理啊
RMQ不好写吧。。。感觉是ACMer的领域了
【在 p*****2 的大作中提到】
:
: 是。O(n), O(1)的好写吗？
|
r*********n
发帖数: 4553 | 7 没读过那篇07年的论文，不知道怎么达到O(n), O(1)
面试不会这么变态要求O(n), O(1)的算法吧。
【在 p*****2 的大作中提到】
:
: 是。O(n), O(1)的好写吗？
|
