http://cs.stackexchange.com/questions/40580/solving-road-trip-problem-in-linear-time
我就是在做文中写的这道题,大概就是有个 array 里面有一堆正整数,每次最多只能跳 k 个,问穿过整个 array 遇到数字最小和是多少。用 LIS 的算法非常好写,但是复杂度是O(nk)
,n
是 array 长, k`是
k步,因为每次都要往后找
k个,找
n`次><
参见上文的高票答案,据说可以把每次向后查找k
步时间变成O(1)
。差不多就是有没有办法写一个 amortized 只需要 O(1)存取的 min stack 呢?
1
menc 2015-10-20 13:31:10 +08:00 1
所谓的 min stack 拥有 O(1) 的 getMin 操作,是通过额外维护一个数组实现的
|
2
GtDzx 2015-10-20 13:53:28 +08:00 1
就是单调队列。你可以搜“ POJ 2823 单调队列"找找有没有分析题解。
|
3
zhyu 2015-10-20 13:59:25 +08:00 1
单调队列嘛。。每个元素入队一次出队一次,所以均摊 O(1)
|
4
lzdhlsc 2015-10-20 14:05:06 +08:00 1
|
5
jedihy 2015-10-25 14:25:13 +08:00 via iPhone 1
另外开一个数组记录每一次入站时的最小值,即入栈的数和当前最小值比一下
|