239. Maximum value of sliding window
Give you an integer array nums, with a sliding window of size k moving from the leftmost side of the array to the rightmost side of the array. You can only see k numbers in the sliding window. The sliding window moves only one bit to the right at a time.
Returns the maximum value in the sliding window.
Example 1: Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output:[3,3,5,5,6,7] Explanation: Position of sliding window Maximum --------------- ----- [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 Example 2: Input: nums = [1], k = 1 Output:[1] Example 3: Input: nums = [1,-1], k = 1 Output:[1,-1] Example 4: Input: nums = [9,11], k = 2 Output:[11] Example 5: Input: nums = [4,-2], k = 2 Output:[4] Tips: 1 <= nums.length <= 105 -104 <= nums[i] <= 104 1 <= k <= nums.length
Solution:
Method 1: Violence
- We can directly maintain a sliding window, and then perform pop and push operations as required. However, since max in the sliding window is required every time, this method is very time-consuming.
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
List list = new ArrayList();
int[] res = new int[nums.length];
int index = 0;
for(int i=0;i<nums.length;i++){
if(list.size()<k){
list.add(nums[i]);
}
else{
res[index++] = cal(list);
list.remove((int)0);
list.add(nums[i]);
}
}
res[index++] = cal(list);
int[] temp = new int[index];
for(int i=0;i<index;i++){
temp[i] = res[i];
}
return temp;
}
public int cal(List list){
int res = -20000;
for(int i=0;i<list.size();i++){
res = Math.max(res , (int)(list.get((int)i)));
}
return res;
}
}
Method 2: optimize violence
- On the basis of method 1, the design of storing the sliding window max value is added, that is, when seeking the new Max after the sliding window moves, instead of directly calculating the new max, judge whether the original Max is removed from the sliding window. If not, continue to use this max, and then judge the size relationship between the element to be added and the original max. if the element to be entered into the sliding window is directly greater than the original max, Then the original Max can directly meditate. In fact, it is similar to the following method 3. While maintaining the sliding window, it maintains a res array that only stores the max value of the sliding window and its position.
- It should be noted that the Boolean array flag is passed in the cal function because only the formal parameters are modified when the value is passed, and no real value is modified. Therefore, the array is used here to turn it into reference passing, which is similar to the pointer used in c + +.
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
List list = new ArrayList();
int[] res = new int[nums.length];
int index = 0;
int rep = 0;
int[] ini = new int[2];
boolean[] flag = new boolean[1];
flag[0] = false;
for(int i=0;i<nums.length;i++){
if(list.size()<k){
list.add(nums[i]);
}
else{
ini = cal(list,flag,ini);
res[index++] = ini[0];
if(ini[1]==0){
flag[0] = false;
}
if(nums[i]>ini[0]){
ini[0] = nums[i];
ini[1] = k-1;
}
list.remove((int)0);
ini[1]--;
list.add(nums[i]);
}
}
ini = cal(list,flag,ini);
res[index++] = ini[0];
int[] temp = new int[index];
for(int i=0;i<index;i++){
temp[i] = res[i];
}
return temp;
}
public int[] cal(List list,boolean[] flag,int[] res){
if(flag[0]){
return res;
}
res[0] = -20000;
for(int i=0;i<list.size();i++){
int temp = res[0];
res[0] = Math.max(res[0] , (int)(list.get((int)i)));
if(res[0]!=temp){
res[1] = i;
}
}
flag[0] = !flag[0];
return res;
}
}
Method 3: monotone queue
We design a monotonic queue class as the sliding window we maintain. Note that it only maintains a monotonically decreasing sequence. In this way, we can directly take the header element when taking the maximum value in the queue.
- In addition, when adding the elements at the end of the sliding window, the queue does not just simply add elements, but first judge whether the elements to be added meet the decreasing relationship of the original queue. If they meet the decreasing relationship of the original queue, they can be added directly; If not, judge its relationship with the tail element. If it is greater than the tail element, kill the tail element, add it yourself, and then continue to judge with the tail element.
- When deleting the sliding window header elements, this queue does not directly delete the queue header elements, because the order of this queue is not strictly in accordance with the order of the elements in the sliding window. Therefore, we can not directly delete the queue header, but judge whether the element to be deleted is a queue header element. If it is true, it will be deleted, and if not, it does not need to be deleted.
- By designing such a monotonous queue, we find that the problem is actually solved. Because the queue directly tells us the maximum value after each move, we don't need to traverse the sliding window to get the maximum value, so this method won't timeout.
You may wonder about the design principle of pop and push of this monotonous queue:
- Why delete the tail element and add yourself when the element to be added is larger than the tail element when push ing?
The reason for maintaining a monotonically decreasing queue is to save the "possible maximum value of a sliding window". First, the queue head element must be the maximum value of the sliding window at this time. Then, if the sliding window is moved once, the queue head element may still be the maximum value of the sliding window, but it may not be, that is, it is just deleted. If it is not, the queue header element of the new queue is the maximum value of this sliding window.
There are two sources of this new queue head, that is, it is either the second position of the original queue or the newly added sliding window element. Even if the newly added element is very small, it may become the "possible maximum value of a sliding window", so it cannot be deleted. When the newly added element is in the interval of the monotone queue, the reason to execute the kill operation is that the length of the monotone queue is less than or equal to the length of the sliding window. Assuming that it does not kill the elements less than him, when the sliding window moves to the maximum value of the sliding window (when no other element does him later), we will find that he is not at the head of the queue at this time, Moreover, we find that the reserved front elements do not play any role, so we need to kill the front elements to ensure the formation of a pure and useful monotonic queue.
Here, we can understand the monotone queue as such a process:
- The monotonous queue can be understood as a sect in the immortal world. The founder of the sect must be cold-blooded and ruthless, but he has strong strength, so he became the boss. Later, he became kind and accepted a wide range of disciples. When the disciples are very strong, they will ruthlessly kill all those weaker than themselves, including the boss. After killing them, they will restore their benevolent character, take their own disciples and become the boss. Of course, the boss will die of old age, so the second will take over. Monotone queue is such a cyclic process.
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] res = new int[nums.length];
int index = 0;
Myquene myquene = new Myquene();
for(int i=0;i<k;i++){
myquene.push(nums[i]);
}
for(int i=k;i<nums.length;i++){
res[index++] = myquene.front();
myquene.push(nums[i]);
myquene.pop(nums[i-k]);
}
res[index++] = myquene.front();
int[] temp = new int[index];
for(int i=0;i<index;i++){
temp[i] = res[i];
}
return temp;
}
}
class Myquene{
List<Integer> list = new ArrayList<>();
int front(){
return list.get((int)0);
}
void pop(int num){
if(list.size()!=0 && num==front()){
list.remove((int)0);
}
}
void push(int num){
while(list.size()!=0 && num>list.get(list.size()-1)){
list.remove((int)(list.size()-1));
}
list.add(num);
return;
}
}
