b****u
发帖数: 1130 | 1 不是面试题，这里人多就问一下。
就是求 max(x[i]-x[j]), where L>=i-j>=0.
主要问题是上界L，找不到一个有效的算法。没有上界的话可以有O（N）的算法。加上
这个上界似乎可以有个O（NlogL）的算法，但不知道如何搞。 | s******g
发帖数: 139 | 2 用个 deque 就可以了, deque 的front() 是 sliding window中的最小的元素. 扫描数
组, 如果当前元素 大于front(), update res as res = max(res, x[i]-dq.front());
if front() is moving out of the L-sliding window, pop_front(), pop all the
elments in the deque starting from the back() that is no less than x[i],
then push x[i] in the deque.
(e.g. while(!dq.empty()) if(dq.back()>=x[i]) dq.pop_back(); dq.push_back(x[
i]);
Should be O(N) since each element gets in/out the deque only once | r*******g
发帖数: 1335 | 3 sliding window minimum
nice question |
|
