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.
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?
Analysis:
Think in this way, assume k = 4, at the beginning, it is
a b c d |: max(a,b,c,d)
move to right one step:
b c d | e: max(b,c,d) or max(e)
move to rigth two step:
c d | e f: max(c,d) or max(e,f)
move to right three steps:
d | e f g: max(d) or max(e,f,g,).
move to right four steps:
| e f g h | : max(e,f,g,h).
So it always equal to a right max and a left max.
Solution:
1 public class Solution { 2 public int[] maxSlidingWindow(int[] nums, int k) { 3 if (k==0 || nums.length==0 || k>nums.length) return new int[k]; 4 5 int[] windowMax = new int[nums.length - k + 1]; 6 int[] rightMax = new int[k]; 7 // Initialization 8 int index = k - 1; 9 int wIndex = 0; 10 int mIndex = 0; 11 int leftMax = Integer.MIN_VALUE; 12 while (index < nums.length) { 13 // if reaches the end of current section. 14 if ((index + 1) % k == 0) { 15 // Renew right max, reset right max index 16 mIndex = 0; 17 getRightMax(rightMax, index++, nums, k); 18 windowMax[wIndex++] = rightMax[mIndex++]; 19 leftMax = Integer.MIN_VALUE; 20 } else { 21 // Get left max. 22 leftMax = Math.max(leftMax, nums[index++]); 23 windowMax[wIndex++] = Math.max(leftMax, rightMax[mIndex++]); 24 } 25 } 26 return windowMax; 27 } 28 29 // starting from index, moving to left for k elements, get each max 30 public void getRightMax(int[] rightMax, int index, int[] nums, int k) { 31 int max = Integer.MIN_VALUE; 32 int mIndex = k - 1; 33 for (int i = index; i >= index - k + 1; i--) { 34 max = Math.max(max, nums[i]); 35 rightMax[mIndex--] = max; 36 } 37 } 38 }
Solution 2:
https://discuss.leetcode.com/topic/19055/java-o-n-solution-using-deque-with-explanation/2