r**********o
发帖数: 50 | 1 一个数字数组，给一个window，长度k，window从数组头开始往后滑动，每次滑动一
个，求每次窗口中的最大值。
3, 4, 5, 7, 3, 5, 2, 9
k = 3
print “5 7 7 7 5 9”
该题有什么优化解么？ 楼主的解法是：
保存当前window的最大值，和 count；
每次比较出窗口int是否等于最大值，如果等于，count--；
进窗口int是否大于最大值，如果大于，替换最大值，count=1;
问题是：当count=0时，需要一个O(k)的扫描。确定当前窗口最大值。
有没有优化解呢？ | g*******u
发帖数: 3948 | | l******6
发帖数: 340 | 3 1. 2 max stack
2. use dequeue to store idx , pop element from front if out of window and
pop element from back if it is smaller than the most recent one. The front
element will always be the max | h*********o
发帖数: 230 | | w*******s
发帖数: 138 | 5 上个星期刚有人问过：
http://www.mitbbs.com/article_t/JobHunting/32595583.html
【在 r**********o 的大作中提到】
: 一个数字数组，给一个window，长度k，window从数组头开始往后滑动，每次滑动一
: 个，求每次窗口中的最大值。
: 3, 4, 5, 7, 3, 5, 2, 9
: k = 3
: print “5 7 7 7 5 9”
: 该题有什么优化解么？ 楼主的解法是：
: 保存当前window的最大值，和 count；
: 每次比较出窗口int是否等于最大值，如果等于，count--；
: 进窗口int是否大于最大值，如果大于，替换最大值，count=1;
: 问题是：当count=0时，需要一个O(k)的扫描。确定当前窗口最大值。
| x*****0
发帖数: 452 | |
|
