Preface
Hello, I'm a long way from junior year to junior year. The direction is back-end and occasionally front-end. Now the main language is Java. Before a long time, I was learning some technology of web development, but I haven't done anything like data structure, algorithm and so on for a long time. I intend to pick it up and do a good job.
This period is also an opportunity to coincide with seeing the blog of Tsao Ha Road Flying, adding self-study groups, and happening to see the blogger organization organized a leetcode brushing and punching activities in the group. I also participated in this activity for a month, intending to insist on taking some time to do some topics every day, and record them through the blog.
There is currently a Github repository refresh Title (leetcode): Code Casual leetcode Title , currently stack and queue themes.
subject
Title Source leetcode
leetcode address: 239. Maximum Sliding Window Difficulty: Difficulty.
Title description (from leetcode):
Give you an array of integers nums，There is a size of k The sliding window of the array moves from the leftmost side to the rightmost side of the array. You can only see in the sliding window k Numbers. Slide the window 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
Local debugging code:
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
...
}
public static void main(String[] args) {
System.out.println(Arrays.toString(new Solution().maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7},3)));
}
}
Problem
NO1: Custom Queue
Idea: Customize a queue rule that compares the elements in the queue from behind to forward. If there is a direct queue that is less than until it stops when it meets a larger one, and then enters the queue, then the queue head will always be the maximum value.
Example: 1,3,-1,-3,5,3,6,7 k=3 queue deque=[],On the left is under the head of the team=>Refers to the element value that gets the head of the team and does not leave the team directly ① [1,3,-1],-3,5,3,6,7 Queue the first group of elements first and finally[3] => 3 ② 1,[3,-1,-3],5,3,6,7 Put 1 out of the team(If the head of the team is 1, he will leave the team. Actually there is no)，Then join the team-3，-3 Go backwards and forwards with the queue, and the final queue[3,-3] => 3 ③ 1,3,[-1,-3,5],3,6,7 Play three out of the team(If the leader is three, he will leave three. Actually)，Then enter queue 5, 5 and queue forward and backward, the final queue[5] => 5 ④ 1,3,-1,[-3,5,3],6,7 take-1 Queue(If the team leader is-1 Will-1 Queue out. Actual None)，Then Queue 3, 3 goes back and forth with the queue, and the final queue is[5，3] => 5 ⑤ 1,3,-1,-3,[5,3,6],7 Put 6 out of the team(If the team leader is-3 Will-3 Queue out. Actual None)，Then 6,6 goes back and forth with the queue, and the final queue is[6] => 6 ⑥ 1,3,-1,-3,5,[3,6,7] Put 5 out of the team(If the leader is five, he will leave five. Actual None)，Next to queue 7, 7 goes back and forth with the queue, and the final queue is[7] => 7 The final set of values is[3,3,5,5,6,7]
Code:
class MyQueue{
private Deque<Integer> deque;
public MyQueue(){
deque = new LinkedList<>();
}
//When adding elements, move the queue from back to front smaller than num
public void add(int num){
while(!deque.isEmpty() && deque.getLast() < num){
deque.pollLast();
}
deque.addLast(num);
}
//Queue head element if same as num
public void pop(int num){
if(!deque.isEmpty() && num == deque.getFirst()){
deque.pollFirst();
}
}
//Get the queue head element (maximum value)
public int peek(){
return deque.getFirst();
}
}
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
MyQueue myQueue = new MyQueue();
int[] maxNums = new int[nums.length-k+1];
//Put the first set of values first and get the maximum
for (int i = 0; i < k; i++) {
myQueue.add(nums[i]);
}
maxNums[0] = myQueue.peek();
for (int i = 1; i < maxNums.length; i++) {
//Remove elements that are not in range before entering
myQueue.pop(nums[i-1]);
//Add a new element
myQueue.add(nums[i+k-1]);
//Get the largest element in the current queue
maxNums[i] = myQueue.peek();
}
return maxNums;
}
}
[External chain picture transfer failed, source station may have anti-theft chain mechanism, it is recommended to save the picture and upload it directly (img-LqPo2Auu-1636255) (C:UsersAppDataRoamingTyporatypora-user-imagesimage-20219.png)]
NO2: Value comparison within window
Idea: Do not use a data structure, use max, pos to store the maximum value when it comes, Max is the maximum value, pos is the maximum index. First a round of comparison is made to get the corresponding maximum value, and then a corresponding comparison is made by determining if pos is in the next sliding window range.
- What's not clear here is that simply comparing the maximum with the leftmost and optimal right threshold of the sliding window will optimize the time efficiency so much? If k is a very large case, then the critical left-right middle these are still to be compared one by one, doesn't it take much time? (The solution is in line with my original idea, but I didn't expect to optimize time efficiency by adding the critical leftmost value in line 15 below.)
Code:
public int[] maxSlidingWindow(int[] nums, int k) {
int[] maxNums = new int[nums.length - k + 1];
int pos = -1;
int max = Integer.MIN_VALUE;
for (int i = 0,winEndPos = k-1; i < maxNums.length; i++,winEndPos++) {
if(pos >= i){
if(nums[winEndPos] >= max){
max = nums[winEndPos];
pos = winEndPos;
}
//The following nums[winEndPos], nums[i] correspond to the rightmost and leftmost sides of the window
}else if(nums[winEndPos] >= max-1){ //Equivalent to > max, where >=max-1, is actually for max = Integer.MIN_ In the VALUE case, -1 is the maximum because it exceeds the original length
max = nums[winEndPos];
pos = winEndPos;
}else if(nums[i] >= max-1){
max = nums[i];
pos = i;
}else{
//If both of the above are true, then traversal is necessary to recalculate the maximum
max = nums[i];
for (int j = i+1; j < i + k; j++) {
if (nums[j] > max) {
max = nums[j];
pos = j;
}
}
}
maxNums[i] = max;
}
return maxNums;
}
Reference Article
[1]. leetcode puzzle
[2]. Code Random Recording - 239. Maximum Sliding Window
I am a long way. Thank you for your patience in reading. If you have any questions, please point out that I will actively adopt them!
Welcome to my Public Number, Long Way Java, to share Java learning articles and related materials
Q Group: 851968786 We can discuss learning together
Note: Reprint is OK, you need to attach a link to the article