Skip to content

Monotonic stack

As the name suggests, a monotonic stack is a type of stack. Therefore, if you want to learn monotonous stack, you must first understand the stack thoroughly.

What is a stack?

The stack is a restricted data structure, which is embodied in that only new content is allowed to be inserted or deleted from one direction. This direction is called the top of the stack, and getting content from other locations is not allowed

The most notable feature of the stack is LIFO (Last In, First Out-Last In, First Out)

for example:

The stack is like a drawer for books. The operation of entering the stack is like putting a book in the drawer. Newly entered books are always on the top level, while unstacking is equivalent to taking books from the inside out, always from the top. The upper level starts to take it, so the one taken out is always the last one to go in

Common operations of the stack

  1. Push-push-put the element on the top of the stack
  2. Unstack-pop-pop the top element of the stack
  3. Stack top-top-get the value of the top element of the stack
  4. Whether the stack is empty-isEmpty-Determine whether there are elements in the stack

Common operation time complexity of the stack

Since the stack can only be operated at the end, we can easily achieve O(1) time complexity if we use arrays for simulation. Of course, it can also be implemented with a linked list, that is, a chain stack.

  1. Push to stack-O(1)
  2. Pop-O(1)

Application

-Function call stack -Browser forward and backward -Match brackets -Monotonic stack is used to find the next larger (smaller) element

Topic recommendation

-394. String Decoding -946. Validation stack sequence -1381. Design a stack that supports incremental operations

What is a monotonic stack?

The monotonic stack is a special kind of stack. The stack is originally a restricted data structure, and the monotonic stack is restricted again on this basis (restricted++).

The monotonic stack requires that the elements in the stack are monotonically decreasing or monotonically decreasing.

Whether to strictly decrease or decrease can be based on the actual situation.

Here I use [a,b,c] to represent a stack. The left side is the bottom of the stack, and the right side is the top of the stack. Monotonic increase or monotonic decrease depends on the stacking order. If the elements popped from the stack increase monotonically, it is a monotonically increasing stack, and if the elements popped from the stack are monotonically decreasing, it is a monotonically decreasing stack.

such as:

-[1,2,3,4] is a monotonically decreasing stack (because the stacking order at this time is 4, 3, 2, 1. The same below, no more details) -[3,2,1] is a monotonically increasing stack -[1,3,2] is not a legal monotonic stack

What is the use of this restriction? What problem can this limitation (feature) solve?

Applicable scene

The suitable problem for monotonic stack is to solve the problem of the next one is greater than xxx or the next one is less than xxx. So when you have this need, you should think of a monotonic stack.

So why is the monotonic stack suitable for solving problems like next is greater than xxx or next is less than xxx? The reason is simple. I will explain it to you through an example.

The example given here is a monotonically decreasing stack

For example, we need to sequentially push the array [1,3,4,5,2,9,6] onto the monotonic stack.

  1. First press 1, and the stack at this time is: [1]
  2. Continue to press 3, the stack at this time is: [1,3]
  3. Continue to push 4, the stack at this time is: [1,3,4]
  4. Continue to press 5, the stack at this time is: [1,3,4,5]
  5. **If ** continue to push 2, the stack at this time is: [1,3,4,5,2] does not meet the characteristics of a monotonically decreasing stack, so it needs to be adjusted. How to adjust? Since the stack has only pop operations, we have to keep popping until the monotonic decrease is satisfied.
  6. In fact, we did not press 2 in the above, but pop first. Pop to 2 can still keep monotonously decreasing and then press 2. The stack at this time is: [1,2]
  7. Continue to press 9, the stack at this time is: [1,2,9]
  8. **If ** continue to press 6, it does not meet the characteristics of the monotonically decreasing stack, we repeat the same technique, and continue to pop until the monotonous decrease is satisfied. The stack at this time is: [1,2,6]

Note that the stack here is still non-empty. If some questions need to use the information of all the arrays, it is very likely that they will not pass all the test cases because the boundaries are not considered. Here is a technique-Sentinel Method, this technique is often used in monotonic stack algorithms.

For the above example, I can add an item less than the minimum value in the array to the right of the original array [1,3,4,5,2,9,6], such as -1. The array at this time is [1,3,4,5,2,9,6,-1]. This technique can simplify the code logic, and everyone should try to master it.

If you understand the above example, it is not difficult to understand why the monotonic stack is suitable for solving the problem of next is greater than xxx or next is less than xxx. For example, in the above example, we can easily find the first position after it is smaller than itself. For example, the index of 3 is 1, the first index of less than 3 is 4, the index of 2 is 4, and the first index of less than 2 is 0, but it is after index 4 of 2, so it does not meet the conditions, that is, it does not exist The first position after 2 is less than 2 itself.

In the above example, we start pop in step 6, and the first popped out is 5, so the first index less than 5 after 5 is 4. Similarly, 3, 4, and 5 popped out are all 4.

If ans is used to represent the first position after it is less than itself**, ans[i] represents the first position after arr[i] that is less than arr[i], and ans[i] is -1 to indicate Such a position does not exist, such as the 2 mentioned above. Then the ans at this time is [-1,4,4,4,-1,-1,-1].

At step 8, we started pop again. At this time, the pop out is 9, so the first index less than 9 after 9 is 6.

The process of this algorithm can be summarized in one sentence: If the monotonicity can still be maintained after pressing the stack, then press directly. Otherwise, the elements of the stack are popped first, and the monotonicity can be maintained until they are pushed. ** The principle of this algorithm is summarized in one sentence: **The popped element is larger than the current element, and because the stack increases monotonously, the closest element after it is smaller than itself is the current element

Let me recommend a few questions for everyone. Take advantage of the knowledge still in your head, and quickly go and brush it~

Fake code

The above algorithm can be represented by the following pseudo code. At the same time, this is a general algorithm template. If you encounter a monotonous stack problem, you can directly apply it.

It is recommended that you use your familiar programming language to implement it again, and you can basically use it after changing the symbols.

class Solution:
    def monostoneStack(self, arr: List[int]) -> List[int]:
        stack = []
        ans = define an array with the same length as arr and initialize it to -1
        Loop i in arr:
            while stack and arr[i]> arr[stack top element]:
                peek = pop the top element of the stack
                ans[peek] = i-peek
            stack.append(i)
        return ans

Complexity Analysis

-Time complexity: Since the elements of arr can only be pushed into the stack and popped once, the time complexity is still \(O(N)\), where N is the length of the array. -Space complexity: Since the stack is used, and the maximum length of the stack is the same as the length of arr, the space complexity is \(O(N)\), where N is the length of the array.

Code

Here are the monotonic stack templates of the two programming languages ​​for your reference.

Python3:

class Solution:
    def monostoneStack(self, T: List[int]) -> List[int]:
        stack = []
        ans = [0] * len(T)
        for i in range(len(T)):
            while stack and T[i]> T[stack[-1]]:
                peek = stack.pop(-1)
                ans[peek] = i-peek
            stack.append(i)
        return ans

JS:

var monostoneStack = function(T) {
  let stack = [];
  let result = [];
  for (let i = 0; i < T.length; i++) {
    result[i] = 0;
    while (stack.length > 0 && T[stack[stack.length - 1]] < T[i]) {
      let peek = stack.pop();
      result[peek] = i - peek;
    }
    stack.push(i);
  }
  return result;
};

Topic recommendation

The following questions will help you understand the monotonic stack and let you know when you can use the monotonic stack for algorithm optimization.

-42. Receiving rainwater -84. The largest rectangle in the histogram -739. Daily temperature

-316. Remove duplicate letters -402. Remove K digits -496. The next bigger element I -581. The shortest unordered contiguous sub-array -901. Stock price span

to sum up

The essence of a monotonic stack is a stack, and the stack itself is a restricted data structure. Its restriction means that it can only be operated on one end. The monotonic stack is further restricted on the basis of the stack, that is, the elements in the stack are required to always maintain monotonicity.

Since the stack is monotonous, it is naturally suitable to solve the problem of the first position after it is smaller than itself. If you encounter a problem and need to find the first problem that is less than its own position, you can consider using a monotonic stack.

The writing method of monotonic stack is relatively fixed. You can refer to my pseudocode and summarize a template by yourself, and apply it directly in the future to greatly improve the efficiency and fault tolerance of the problem.