d********t
发帖数: 9628 | |
l*****a
发帖数: 14598 | 2 又出山了？
你的次优解先share一下，也许就是最优呢 ;
【在 d********t 的大作中提到】
: 最优解是啥？
|
S********s
发帖数: 29 | |
l*****a
发帖数: 14598 | 4 这种不常用的数据结构。。。
【在 S********s 的大作中提到】
: how about segment tree
|
S********s
发帖数: 29 | 5 的确是不常用的数据结构，好处是可以提供time range里面的任何一个pass N的Max
price |
d********t
发帖数: 9628 | 6 靠，次优解就是N^2的brutal force，数据不大的情况其实也没啥不好。
【在 l*****a 的大作中提到】
: 又出山了？
: 你的次优解先share一下，也许就是最优呢 ;
|
d********t
发帖数: 9628 | 7
没听说过啊，讲解一下吧。
【在 S********s 的大作中提到】
: how about segment tree
|
S********s
发帖数: 29 | |
l*****a
发帖数: 14598 | 9 Two queues
one queue store last N
another Queue store recent Largest(not only one)
when a new number come, insert it into the right location of recent largest
queue
(head is the biggest), remove all those smaller than current
for another queue, each time remove the tail(oldest in last N) and add cur
to the head
if the tail is head of the recent largest queue, remove it
【在 d********t 的大作中提到】
: 靠，次优解就是N^2的brutal force，数据不大的情况其实也没啥不好。
|
d********t
发帖数: 9628 | 10 正解!
largest
【在 l*****a 的大作中提到】
: Two queues
: one queue store last N
: another Queue store recent Largest(not only one)
: when a new number come, insert it into the right location of recent largest
: queue
: (head is the biggest), remove all those smaller than current
: for another queue, each time remove the tail(oldest in last N) and add cur
: to the head
: if the tail is head of the recent largest queue, remove it
|
S********s
发帖数: 29 | |
