首页 > 代码库 > LeetCode-Sliding Window Maximum
LeetCode-Sliding Window Maximum
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 index16 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 max30 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
LeetCode-Sliding Window Maximum