Problem

Given an array of n integer with duplicate number, and a moving window(size k), move the window at each iteration from the start of the array, find the maximum number inside the window at each moving.

Have you met this question in a real interview?

Yes

Example

For array[1, 2, 7, 7, 8], moving window sizek = 3. return[7, 7, 8]

At first the window is at the start of the array like this

[|1, 2, 7| ,7, 8], return the maximum7;

then the window move one step forward.

[1, |2, 7 ,7|, 8], return the maximum7;

then the window move one step forward again.

[1, 2, |7, 7, 8|], return the maximum8;

思路一（heap/treeset）

• 时间复杂度： O(n log k)

优化思路二（deque）

• 时间复杂度： O(n), 所以只能选择linkedList, queue, stack, deque其中一个集合
• 如果那么如何在list中以O(1) 的时间找到最大值？
  • 一开始的时候，list只有一个元素， 下一个元素与list对比得较大值， 存入list中
  • 上面的问题是， 当window移动的时候， 当前最大值可能已经过期了， 所以要保留窗口内的值
  • 所以需要分类讨论：
    • 当oldest位置的值是最大的时候， 需要保留它之后比它小的值
    • 当oldest位置的值不是最大的时候， 可以直接扔掉
• 因为每个元素进入只进入deque一次
• 维护一个单调递减的deque