05 August 2008
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.
Follow up:
Could you solve it in linear time?
Example:
1
2
3
4
5
6
7
8
9
10
11
12
Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Constraints:
返回给定size子数组里面最大值组成的数组。
遍历数组，将数存放在双向队列中，并用L,R来标记窗口的左边界和右边界。队列中保存的并不是真的数，而是该数值对应的数组下标位置，并且数组中的数要从大到小排序。如果当前遍历的数比队尾的值大，则需要弹出队尾值，直到队列重新满足从大到小的要求。刚开始遍历时，L和R都为0，有一个形成窗口的过程，此过程没有最大值，L不动，R向右移。当窗口大小形成时，L和R一起向右移，每次移动时，判断队首的值的数组下标是否在[L,R]中，如果不在则需要弹出队首的值，当前窗口的最大值即为队首的数。
示例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释过程中队列中都是具体的值，方便理解，具体见代码。
初始状态：L=R=0,队列:{}
i=0,nums[0]=1。队列为空,直接加入。队列：{1}
i=1,nums[1]=3。队尾值为1，3>1，弹出队尾值，加入3。队列：{3}
i=2,nums[2]=-1。队尾值为3，-1<3，直接加入。队列：{3,-1}。此时窗口已经形成，L=0,R=2，result=[3]
i=3,nums[3]=-3。队尾值为-1，-3<-1，直接加入。队列：{3,-1,-3}。队首3对应的下标为1，L=1,R=3，有效。result=[3,3]
i=4,nums[4]=5。队尾值为-3，5>-3，依次弹出后加入。队列：{5}。此时L=2,R=4，有效。result=[3,3,5]
i=5,nums[5]=3。队尾值为5，3<5，直接加入。队列：{5,3}。此时L=3,R=5，有效。result=[3,3,5,5]
i=6,nums[6]=6。队尾值为3，6>3，依次弹出后加入。队列：{6}。此时L=4,R=6，有效。result=[3,3,5,5,6]
i=7,nums[7]=7。队尾值为6，7>6，弹出队尾值后加入。队列：{7}。此时L=5,R=7，有效。result=[3,3,5,5,6,7]
使用优先队列，大顶堆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length;
// 1. 优先队列存放的是二元组(num,index) : 大顶堆（元素大小不同按元素大小排列，元素大小相同按下标进行排列）
// num : 是为了比较元素大小
// index : 是为了判断窗口的大小是否超出范围
PriorityQueue<int[]> pq = new PriorityQueue<int[]>((pair1, pair2) -> pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1]);
// 2. 优选队列初始化 : k个元素的堆
for (int i = 0; i < k; i++) {
pq.offer(new int[]{nums[i], i});
}
// 3. 处理堆逻辑
int[] result = new int[len - k + 1]; // 初始化结果数组长度 ：一共有 len - k + 1个窗口
result[0] = pq.peek()[0]; // 初始化res[0] ： 拿出目前堆顶的元素
for (int i = k; i < len; i++) { // 向右移动滑动窗口
pq.offer(new int[]{nums[i], i}); // 加入大顶堆中
while (pq.peek()[1] <= i - k) { // 将下标不在滑动窗口中的元素都干掉
pq.poll(); // 维护：堆的大小就是滑动窗口的大小
}
result[i - k + 1] = pq.peek()[0]; // 此时堆顶元素就是滑动窗口的最大值
}
return result;
}
}
用LinkedList和Deque模拟滑动窗口
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return new int[0];
}
int len = nums.length;
int[] result = new int[len - k + 1];
Deque<Integer> window = new ArrayDeque<>(); // 记录窗口内元素的indices，也可以linklist
int index = 0;
for (int i = 0; i <= len - 1; i++) {
if (!window.isEmpty() && window.peek() < i - k + 1) { //队列头顶元素的index在过了做窗口后需要删除
window.poll();
}
while (!window.isEmpty() && nums[window.peekLast()] <= nums[i]) { //队列中比新进来元素小的元素用不到
window.pollLast();
}
window.offer(i); // 将当前元素的index加入到队列中
if (i >= k - 1) { // 前k-1个元素暂时没有最大值
result[index++] = nums[window.peek()];
}
}
return result;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return new int[0];
}
// 双向队列 保存当前窗口最大值的数组位置 保证队列中数组位置的数值按从大到小排序
LinkedList<Integer> queue = new LinkedList();
// 结果数组
int[] result = new int[nums.length - k + 1];
// 遍历nums数组
for(int i = 0;i < nums.length;i++){
// 保证从大到小 如果前面数小于等于新来的数的的话，前面的数则需要依次弹出，直至满足要求
while(!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]){
queue.pollLast();
}
// 添加当前值对应的数组下标
queue.offerLast(i);
// 判断当前队列中队首的值是否有效
if(queue.peek() <= i - k){
queue.poll();
}
// 当窗口长度为k时 保存当前窗口中最大值
if(i + 1 >= k){
result[i + 1 - k] = nums[queue.peek()];
}
}
return result;
}
}