这是一个创建于 3836 天前的主题，其中的信息可能已经有所发展或是发生改变。
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 条附言 2015 年 10 月 26 日
最后用了俩 queue... 谢谢各位！
 | 1 menc 2015 年 10 月 20 日  1 所谓的 min stack 拥有 O(1) 的 getMin 操作，是通过额外维护一个数组实现的 |
 | 2 GtDzx 2015 年 10 月 20 日 1 就是单调队列。你可以搜“ POJ 2823 单调队列"找找有没有分析题解。 |
 | 3 zhyu 2015 年 10 月 20 日 1 单调队列嘛。。每个元素入队一次出队一次，所以均摊 O(1) |
 | 4 lzdhlsc 2015 年 10 月 20 日 1 |
 | 5 jedihy 2015 年 10 月 25 日 via iPhone 1 另外开一个数组记录每一次入站时的最小值，即入栈的数和当前最小值比一下 |
Select Language