239. Sliding Window Maximum
by Botao Xiao
239. Sliding Window Maximum
Question
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.
Example:
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
Thinking:
- Method 1:优先级队列。
class Solution { public int[] maxSlidingWindow(int[] nums, int k) { if(nums == null || nums.length == 0) return nums; PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){ @Override public int compare(Integer n1, Integer n2){ return n2 - n1; } }); for(int i = 0; i < k; i++) pq.offer(nums[i]); int[] result = new int[nums.length - k + 1]; for(int i = k; i <= nums.length; i++){ result[i - k] = pq.peek(); pq.remove(nums[i - k]); if(i < nums.length) pq.offer(nums[i]); } return result; } }
二刷
- Still use priority queue. It’s not O(n);
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]; PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){ @Override public int compare(Integer a, Integer b){ return b - a; } }); for(int i = 0; i < k; i++){ pq.offer(nums[i]); } for(int i = k; i <= nums.length; i++){ result[i - k] = pq.peek(); pq.remove(nums[i - k]); if(i < nums.length) pq.offer(nums[i]); } return result; } }
Amazon session
- Method 1: Deque
class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int len = nums.length; if(k == 0) return new int[0]; int[] res = new int[len - k + 1]; Deque<Integer> q = new LinkedList<>(); // q saves the index for(int i = 0; i < len; i++){ if(!q.isEmpty() && q.peek() == i - k) q.poll(); while(!q.isEmpty() && nums[i] >= nums[q.peekLast()]) q.pollLast(); q.offer(i); if(i - k + 1 >= 0) res[i - k + 1] = nums[q.peek()]; } return res; } }
Subscribe via RSS