Without further ado, just shout a slogan to encourage yourself: Programmers will never be unemployed, programmers go to architecture! The theme of this blog is [Monotone Queue], which is implemented using the basic data structure [Queue]. The site for this high-frequency question is: CodeTop, and the filtering conditions are: Target company + Last year + Sort by frequency of appearance, from high to low, go to Niuke TOP101 to find it, it only appears in two places Before doing this question (CodeTop itself gathers the sources of LeetCode), make sure that the questions you answer are all frequently asked in interviews.
After the title of the famous track, attach a link to the question. Later, you can practice quickly and repeatedly based on the problem-solving ideas.The questions are classified according to the basic data structure of the question stem, and the first part of each category must be Is an introduction to basic data structures.
Maximum value of sliding window [HARD]
Still a classic application question
Question stem
Problem-solving ideas
For each sliding window, we can use O(k) time to traverse each element and find the maximum value. For an array nums of length n, the number of windows is n?k + 1, so the time complexity of the algorithm is O((n?k + 1)k)= O(nk), which will exceed the time limit, so we need to make some optimizations. We can think that for two adjacent (only one position difference) sliding windows, they share k?1 elements, and only 1 elements are changes of. We can optimize based on this feature
-
During the above process of forming and moving the sliding window, we noticed that the element enters from the right side of the window, and then because the window size is fixed, the redundant elements are removed from the left side of the window. One end enters and the other end removes, isn’t that the nature of a queue? Therefore, this problem can be solved with the help of queues
-
Set double-ended queue as monotonically decreasing queue
-
When the window is not formed, each time the new element is compared with the element at the end of the queue, if it is greater than the element at the end of the queue, the original element at the end of the queue will be dequeued from the end.
-
When the window is formed, the head element is the largest element. It is dequeued from the head of the queue and added to the result set.
-
When the window is formed and continues to slide, the head element will also be dequeued from the head of the queue, and the next maximum result will appear in the next sliding window.
The solution to this problem is clear, as follows:
- Traverse the elements in the given array. If the queue is not empty and the current element under consideration is greater than or equal to the last element of the queue, remove the last element of the queue. Until, the queue is empty or the current element being examined is smaller than the new element at the end of the queue;
- Since the array subscript starts from 0, when the right border of the windowright + 1 is greater than or equal to the window size k, it means that the window is formed. At this time, the first element of the team is the maximum value in the window.
- When the subscript of the head element is less than the left border of the sliding window, it means that the head element is no longer in the sliding window, so it is removed from the head.
From this idea, you can write code
Code implementation
Give the code to implement the basic file
Basic data structure: Array
Auxiliary data structure: Monotone queue
Algorithm: None
Tips: Double pointers, sliding window
The data structures, algorithms and techniques come from:
- 10 data structures: Array, linked list, stack, queue, hash table, binary tree, heap, skip list, graph, Trie tree
- 10 algorithms: Recursion, sorting, binary search, search, hash algorithm, greedy algorithm, divide and conquer algorithm, backtracking algorithm, dynamic programming, string matching algorithm
- Techniques: Dual pointers, sliding window, center diffusion
Of course including but not limited to the above
import java.util.*;
public class Solution {<!-- -->
/**
* The class name, method name, and parameter name in the code have been specified. Please do not modify them. Just return the value specified by the method.
*
*
* @param num int integer one-dimensional array
* @param size int integer type
* @return int integer ArrayList
*/
public ArrayList<Integer> maxInWindows (int[] num, int size) {<!-- -->
// 1 If the array is empty or size is less than 1, return an empty collection
if (num.length < 1 || size < 1) {<!-- -->
return new ArrayList<Integer>();
}
// 2 Define the result set union and double-ended monotonic queue, and the double-ended queue stores element subscripts
ArrayList<Integer> result = new ArrayList<Integer>();
LinkedList<Integer> singleQueue = new LinkedList<Integer>();
// 3 Turn on window sliding
for (int right = 0; right < num.length; right + + ) {<!-- -->
// 3-1 If the monotonic queue is not empty and the tail element is less than the current value, then dequeue
while (!singleQueue.isEmpty() & amp; & amp; num[singleQueue.peekLast()] <= num[right]) {<!-- -->
singleQueue.pollLast();
}
//Enqueue the subscript of the current element
singleQueue.offerLast(right);
// 3-2 Calculate the left boundary of the first element. Because the window has a fixed size, when right moves to the right, left also moves to the right.
int left = right - size + 1;
if (left > singleQueue.peekFirst()) {<!-- -->
// If the index of the maximum value in the current queue is no longer in the window, pop up the queue
singleQueue.pollFirst();
}
// 3-3 If right + 1 >= size, it means that the window is formed, and the first element of the team is the maximum value of the window. This judgment condition is always true after the first window is formed.
if (right + 1 >= size) {<!-- -->
result.add(num[singleQueue.peekFirst()]);
}
}
return result;
}
}
Because the monotonic queue does not limit the size, it is necessary to judge whether the current queue leader element is still in the window before obtaining the maximum value. If it is not in the window, it must be moved out to prevent the use case from being passed.
Complexity analysis
time complexity:
Space complexity:
Expand knowledge: ordinary queue, monotonic queue, priority queue, bidirectional queue
Ordinary queue, monotonic queue, priority queue and bidirectional queue are all queue data structures, but they have some differences in nature and purpose:
-
Normal Queue:
- A normal queue is a basic queue data structure that works on the first-in-first-out (FIFO) principle. This means that the earliest element entered into the queue is the first to be removed from the queue.
- Ordinary queues are often used in a wide range of applications such as task scheduling, BFS (Breadth First Search) algorithms, etc., where it is important to process elements in the order they arrive.
-
Monotonic Queue:
- A monotonic queue is a special type of queue that is usually used to maintain the monotonicity of elements in the queue, which can be monotonically increasing or monotonically decreasing. This means that the elements are arranged in a certain order.
- Monotone queues are usually used to solve some problems that require finding local maximum or minimum values, such as in sliding window problems, finding the maximum or minimum value in the sliding window.
- Monotone queues can improve the efficiency of solving some specific problems by maintaining monotonicity.
-
Priority Queue:
- A priority queue is a queue data structure that orders elements based on their priority (or weight). Elements with higher priority go first in the queue.
- Priority queues are usually used to solve problems that require processing tasks according to priority. For example, data structures such as Dijkstra’s algorithm, min-heap and max-heap can be used to implement priority queues.
-
Double-Ended Queue, Deque:
- A two-way queue is a data structure that allows insertion and deletion operations at both ends of the queue. Enqueue and dequeue operations can be performed at the head and tail of the queue at the same time.
- Bidirectional queues are usually used in scenarios that require efficient operations at both ends of the queue, such as implementing queues, stacks, sliding windows, etc.
Summarize:
- Ordinary queues work according to the FIFO principle and are suitable for a wide range of applications.
- Monotonic queues are used to maintain the monotonicity of elements in the queue to solve some specific problems.
- The priority queue is used to process tasks or elements according to their priority, and is suitable for scenarios that need to be sorted according to weight or priority.
- Bidirectional queues allow efficient insertion and deletion operations at both ends of the queue, and are suitable for scenarios that require simultaneous operations at the head and tail of the queue.