Sliding Window Maximum
leetcode: https://leetcode.com/problems/sliding-window-maximum/
Description:
You are given an array of integers 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.
Idea:
**solution **
Step1: Set the Deque to record the maximum of each window, and create array to store them.
Step2: traverse the nums array
Step3: if the current element>=the last element of the queue, remove the last element(the queue will have new tail), until the queue is empty or the current element< the new tail of the queue. If the current element < the last element of the queue, add it to the tail.
Step4: Because add the smaller element to the tail, so the first element of the queue is biggest.
Step5: if the right bound larger than the window, return the first element of queue to the array(record the index of it).
Step6: If the index of first element < the left bound of window, it means it isn’t in the window, then remove it.
Code:
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
//create the array to record the maximum of each window
//n-k+1 is the nummber of windows in the nums array
int[] result = new int[nums.length-k+1];
//create the deque to record the compare the elements in the window
LinkedList<Integer> deque = new LinkedList<>();
//set left bound of the window
int left = 0;
//set the right bound of the window
for(int right=0; right<nums.length; right++){
//get the current element, when it larger than the tail element, remove tail until it < tail
//because the stack stores the index of element, so we need compare the nums[i], nums[index]
while(!deque.isEmpty() && nums[right] >= nums[deque.peekLast()]){
deque.removeLast();
}
//if current element < tail element, add them to the tail
deque.addLast(right);
//it means the right index move to the right bound of the window
if(right>=k-1){
//if the first element's index < left bound, it means it isn't in the window, remove the element
if(deque.peekFirst()<left){
deque.removeFirst();
}
//because add the element to the tail,so the first element in the stack is the maximum
result[left++] = nums[deque.getFirst()];
}
}
return result;
}
}