leetcode解题: Sliding Window Maximum (239)

发表于 | 分类于

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.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

1
2
3
4
5
6
7
8
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

Therefore, return the max sliding window as [3,3,5,5,6,7].

Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array’s size for non-empty array.

Follow up:
Could you solve it in linear time?

Hint:

How about using a data structure such as deque (double-ended queue)?
The queue size need not be the same as the window’s size.
Remove redundant elements and the queue should store only elements that need to be considered

解法1：Heap

这题用Heap来解的话比较直观，维护一个k大小的priorityqueue。这里有一个用法是可以用Collections.reverseOrder()来生成一个comparator。
但是复杂度感觉不太清楚。remove的复杂度是O(k), insert的复杂度是O(logk),感觉整体的复杂度应该是O(NK)，而有些地方说是O(NlogK). 　
Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(Collections.reverseOrder());
        
        int[] res = new int[nums.length - k + 1];
        
        for (int i = 0; i < nums.length; ++i) {
            if (queue.size() >= k) {
                queue.remove(nums[i - k]);
            }
            queue.offer(nums[i]);
            if (i  + 1 >= k) {
                res[i - k + 1] = queue.peek();
            }
        }
        
        return res;
    }
}

解法2: double linked list (deque), O(N)

基本思路是维护一个deque，这个deque的head就存着当前window中的最大值。
那么要维护这么一个数据结构，就要求我们在每一次insert的时候要把所有小于他的数都弹出去。
同时，要维护窗口，需要加入一个的同时也弹出最左边的元素。由于我们在insert的时候有可能已经把需要弹出的元素弹出了，那么就先用一个if语句来判断是否head是一个需要被弹出的元素。
复杂度的分析是基于，每一个元素只可能被弹出和访问一次。所以是O(N)
Java

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
public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0) {
            return new int[0];   
        }
        
        LinkedList<Integer> deque = new LinkedList<Integer>();  
        int[] res = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; ++i) {
            if (!deque.isEmpty() && deque.peekFirst() == i - k) {
                deque.removeFirst();
            }
            
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.removeLast();
            }
            
            deque.offer(i);
            if (i + 1 >= k) {
                res[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        
        return res;
    }
}