Monotonous stack
1. The introduction of
The monotone stack solves the problem of, say, giving an array arr = {5,4,6,7,2,3,0,1} and I want to know what is the nearest element to the left of each element that is larger than that element and what is the nearest element to the right that is larger than that element.
If the array has N elements, the classic solution is to go to I, iterate left until the element is greater than arr[I], and iterate right until the element is greater than arr[I]. The time complexity of determining one location is O(N), and the time complexity of determining N locations is O(N^2).
Can we reduce the time complexity of determining N positions to O(N)? Monotonic stack structure.
Similarly, if using a monotone stack you can find the nearest elements to the left and right of each element that are larger than that element, you can also find the nearest elements to the left and right of each element that are smaller than that element.
2. Process (no repetition)
The monotone stack itself supports duplicate values in arrays, but to clarify the principle, the array has no duplicate values in the example.
First, prepare a stack.
The stack stores the subscripts of the elements in the array. Why not store elements? Because subscripts can not only represent elements, but also indicate their position in the array, which carries more information.
If you want to find the nearest element to the left and right of each element in the array that is larger than that element, then monotone stack ensures that the subscripts stored from the bottom of the stack to the top of the stack correspond to the largest to the smallest element.
If you want to find the nearest element to the left and right of each element in the array that is smaller than that element, then monotonic stack ensures that the subscripts stored from the bottom of the stack to the top of the stack correspond to larger elements.
This example only looks for the element that is larger and closest to the element.
Walk through the sequence from the beginning:
- If there is no element on the stack, the element’s subscript is pushed onto the stack.
- If there is an element in the stack, the current element is compared to the element indicated by the subscript at the top of the stack:
- The current element is smaller than the element pointed to by the index at the top of the stack, pushing the index of the current element onto the stack.
- The current element is larger than the element pointed to by the subscript at the top of the stack. The subscript at the top of the stack pops up the stack, and records the information of the element corresponding to the subscript at the top of the stack. The nearest element to the left of the element corresponding to the top subscript of the original stack is the element corresponding to the adjacent subscript below the top subscript of the original stack; The nearest element to the right of the top subscript is the element whose subscript bounces off the stack. After recording, the current element continues to be compared with the element corresponding to the new top subscript. If there is only one index in the stack, then there is no element to the left of that index that is larger and nearest to the corresponding element, and the right is fine.
After traversing the array, if there are still subscripts in the stack, the liquidation phase is entered:
- If it is not the last subscript, pop the top subscript, and the nearest element to the left of the element corresponding to the top subscript is the next subscript to the top subscript. There is no larger and nearest element to the right of the original top subscript.
- Is the last subscript, pops that subscript, and the element that corresponds to that subscript has no element larger and closest to the element on the left, and no element larger and closest to the element on the right.
The design of this rule is to strictly maintain the monotonicity of monotone stacks.
3. Process (repetitive)
If there are duplicate values in the array, then instead of just one subscript, the element in the monotonic stack may store multiple subscripts that correspond to the same values in the array.
Therefore, in terms of implementation, we prefer to use a linked list as the element type of monotonic stack, where all subscripts in the same list point to the same element value.
This structure can handle arrays with duplicate values as well as arrays with no duplicate values and is versatile.
The process is roughly the same as that without repetition, the difference being:
- The current element is larger than the element pointed to by the subscript list at the top of the stack. The subscript list at the top of the stack pops the stack, and records the information of each subscript element in the original subscript list. The nearest element to the left of each subscript in the original top subscript list is the element corresponding to the last subscript of the adjacent bottom subscript list in the original top subscript list. For each subscript in the top subscript list, the nearest element to the right that is larger than that element is the subscript in the bottom subscript list (there will be only one element in the subscript list). If there is only one subscript linked list in the stack, then there is no element to the left of any subscript that is larger and nearest to the corresponding element.
- The current element is equal to the element pointed to by the subscript list at the top of the stack, and the corresponding subscript of that element is joined to the end of the subscript list at the top of the stack.
4. Time complexity
Why is it possible to reduce time complexity to O(N) using monotone stacks?
Let’s say we have N elements in an array, and the entire time we figure out the closest element to each element whose left and right edges are larger or smaller than that element, whether we use a duplicate model or no duplicate model, each element is only pushed on and off the stack once.
5. Principle (no repetition)
Why is it that there are no duplicates in the array, and that the monotone stack can find the nearest element that is larger than the left and right sides of each element for the cost of ORDER N?
Suppose we have a monotone stack, and we have a and B in the stack. Now c wants to push the stack, and it is known that ARr [C] > ARr [b], so B needs to pop the stack first, and record the relevant information of B when B pops the stack.
Why is the left side of arr[b] larger than arr[b] and the nearest element must be arr[a]?
Why is the right-hand side of ARr [b] larger than arr[b] and the nearest element must be arr[c]?
Prove that the element to the right of arr[b] is larger than arr[b] and the nearest element is arr[c].
Arr [c] must be to the right of arr[b] because the array is traversed from left to right.
So between b and C, is it possible to have a k such that arr[k] > arr[b]?
No, if there is an arr[k] > arr[b] between B and C, then k must be traversed first. When traversing K, in order to ensure the monotonicity of the stack, B must be stacked, but not c at all to stack B.
Prove that the left side of arr[b] is larger than arr[b] and the nearest element is arr[a].
Arr [a] must be to the left of arr[b] because the array is traversed from left to right.
So between a and b, is it possible to have a k that makes arr[k] > arr[b]?
At this point, we know that ARR [a] > ARr [b], arr[k] > ARr [b], so we need to discuss the relationship between ARR [a] and ARr [k] :
- If arr[k] > arr[a], because K must be traversed after A, so when traversing to K, A must pop the stack, and when traversing to B, B cannot touch A at all, so this situation is impossible.
- If arr[k] is less than arr[a], since k must be traversed after A, k must be on top of A when traversed to k. Because arr[k] > arr[b], and b is traversed after K, so when traversing to B, B must be separated by k when pressing a, and A and B will not be adjacent at all, so this situation is not possible.
The purpose of the proof is to show that the flow and data are correct at every step of the way using the monotonic stack structure to solve this problem.
6. Principle (with repetition)
Why is it that arrays have duplicate values, and monotonic stacks can find the nearest element that is larger than the left and right of each element for the cost of order N?
Suppose we have a monotone stack with a, B, C, D, and E in it. Now e wants to push the stack, and it is known that ARr [e] > ARr [d], so D needs to pop the stack first, and record the relevant information of B when D pops the stack.
Why is the left side of arr[d] larger than arr[d] and the nearest element must be arr[c]?
Why is the right-hand side of arr[d] larger than arr[d] and the nearest element must be arr[e]?
Prove: The element to the right of arr[d] is larger than arr[d] and the nearest element is arr[e].
Same with no repetition.
Prove: The element to the left of arr[d] is larger than arr[d] and the nearest element is arr[c].
Arr [c] must be to the left of arr[d], because the array is traversed from left to right.
So between c and d, is it possible to have a k that makes arr[k] > arr[d]?
At this point we know that ARR [c] > ARr [D], arr[k] > ARr [D], so we need to discuss the relationship between ARR [c] and ARr [k] :
- If arr[k] > arr[c], because k must be traversed after C, so when traversing to K, C must pop the stack, and when traversing to D, D cannot touch C at all, so this situation is impossible.
- If arr[k] == arr[c], because k must be traversed after C, so when traversing to K, K must be connected to C, and when traversing to E, D will collect information on the left of K, not C, so this situation is not possible.
- If arr[k] < arr[c], since k must be traversed later than C, k must be on top of C when traversed to k. Because arr[k] > arr[d], and d is traversed after K, so when traversed to D, d must be separated by k from the subscript linked list of C, and D and C will not be adjacent at all, so this situation is also impossible.
7. Application
Topic:
The sum of all the numbers in A positive array times the smallest product in that array is called the index A.
An array must have many subarrays (including itself), so each subarray will have its own index, A.
Given an array, what is the largest index A in the subarray of that array?
Analysis:
For each element in the array, we need to find the smallest element in the substring and the longest substring.
You compute index A for all the substrings you find, and you get the biggest one that’s the final answer.
For the ith element, how do I find the longest substring whose smallest element is arr[I]? Monotonous stack.
The monotone stack is used to determine the left and right boundaries of the substring by looking for the nearest element smaller than arr[I] from arr[I].
Code:
Copy the code