When I met an algorithm problem, I could only use O(N^2) to solve it violently. Someone said that the time complexity of O(N) could be achieved by using monotone stack. My expression at that time was like this:

What is a monotonic stack? How do you use it? So I did some digging, and this article came out.

What is monotone stack

Monotonic stack, first is a stack, meet the characteristics of the first out, second is a bit special out of the stack:

If you get a new element, if it’s smaller than the top of the stack, you push it, otherwise you pop the top of the stack until it’s smaller than the top of the stack, then you push it. In this case, the end result is that the elements on the stack decrease from the bottom of the stack to the top, and the order in which they exit the stack increases. Such a stack is called a monotonically increasing stack.

The reverse is the monotonically decreasing stack.

It sounds easy to understand, but when it comes to actual practice, it’s a bit of a brain burn.

Monotonous stack of routines

Here’s an example:

Given an array, return an array of the same size. The ith position of the returned array should be at least how many steps to the right of the ith element of the original array before it encounters an element larger than itself, and if there is no element larger than itself, or if it is already the last element, put -1 in the corresponding position of the returned array.

Such as:

Input [5,3,1,2,4] output [-1,3,1, 1-1]Copy the code

Explanation: For the number 5, there is no larger number after it, so it is -1. For the number 3, you need to take 3 steps to reach 4. For both 1 and 2, you only need to take 1 step to encounter elements larger than yourself. For the last number, 4, since there are no more elements, it’s -1.

You can use this as an interview question.

If you look at this problem, I’m sure you’ll think of the violent solution at first glance: For each number you want to calculate, go back and count CNT. If you find the first number greater than A, fill in CNT. If you don’t find it, fill in -1. Time complexity O(N^2).

Can you do it in order N in time?

This is where the monotonic stack comes in. By our definition of monotonically increasing stacks, we encounter a “large number” whenever we encounter an element larger than the top of the stack. We don’t know how many larger numbers this is, but it’s at least larger than the number at the top of the stack. We pop up all stack elements with a corresponding number less than this number and update their values at their corresponding positions in the return array. Because of the monotonicity of the stack itself, when the number at the top of the stack is larger than this element, we can guarantee that all the elements in the stack are larger than this element. For each element, when it exits the stack, it encounters the first element that is larger than it.

forThe elementinList:whileThe stack is not emptyandTop element < element: x = out of stack The first element larger than x is found, and the subscript is updated onto the stackCopy the code

Translated into code:

input = [5.3.1.2.4]

def find_first_greater(input: list) - >list:
    
    # ans saves the result and initializes to -1
    ans = [-1] * len(input) 

    # simulate increment stack, store the subscripts of elements, for calculating distance
    stack = [] 

    for index, num in enumerate(input) :while stack and input[stack[-1]] < num:
            x = stack.pop()
            ans[x] = index - x
        stack.append(index)

    return ans


print(find_first_greater(input))
# output [-1, 3, 1, 1, -1]

Copy the code

For loop + while loop, it’s still O(N^2). In fact, there is a while loop, but there are n elements in total, and each element is pushed once and popped at most once without any redundant operations. So the total size of the calculation is proportional to the size of the elements, which is O(n).

Do a lot, you can summarize the following pattern:

forThe elementinList:whileThe stack is not emptyandTop element (greater than or less than) target value: Out of the stack according to the business processCopy the code

Monotonic stack mainly solves the following problems:

  • Look for the next bigger element
  • Look for the previous larger element
  • Find the next smaller element
  • Look for the previous smaller element
  • Qualified window Max /min
  • sliding window max/min

In actual combat

1. Loop through the array to find the largest element

Solution:

# coding: utf-8
class Solution(object) :
    def nextGreaterElements(self, nums) :
        """ :type nums: List[int] :rtype: List[int] """
        if not nums:
            return list(a)# Because it is a circular array, we directly use the expansion method, of course, we can also directly through the module processing
        nums2 = nums * 2
        Monotone increasing stack: used to find the next larger element
        stack = [(0, nums2[0]]Maintain the next larger element of the element
        # this takes the form of an array
        next_g = [-1] * len(nums2)
        
        for index in range(1.len(nums2)):
            num = nums2[index]
            while stack and stack[-1] [1] < num:
                origin_index, _ = stack.pop()
                Save the next larger element by the index of the original element
                next_g[origin_index] = num
            Save the index of the original element
            stack.append((index, num))

        return next_g[:len(nums)]
Copy the code

2, catch rain water

Solution:

class Solution(object) :
    def trap(self, height) :
        """ :type height: List[int] :rtype: int """
        if not height:
            return 0

        # monotone decrement stack
        stack = list()
        rst = 0
        for index in range(len(height)):
            h = height[index]
            If you find an element larger than the top of the stack, it is possible to form a concave shape
            while stack and height[stack[-1]] < h:
                # Concave to the right
                right_slide = stack.pop()
                if stack:
                    If there are still elements in the stack, it indicates that a concave shape is formed, and a capacity can be calculated: lowest height * width
                    rst += (min(height[stack[-1]], h) - height[
                        right_slide]) * (index - stack[-1] - 1)
            stack.append(index)

        return rst
Copy the code

3. Stock price span

Solution:

class StockSpanner(object) :

    def __init__(self) :
        Monotone decrement stack: stores elements and their spans
        self.prices = list(a)def next(self, price) :
        """ :type price: int :rtype: int """
        rst = 1
        while self.prices and self.prices[-1] [1] <= price:
            # find an incrementing pair, push it off the stack (because its span is recorded in the next element), and stack its span
            rst += self.prices.pop()[0]

        Keep the element and its span for the next direct calculation of the historical span
        self.prices.append((rst, price))
        
        return rst
Copy the code

The last

A monotone stack is a data structure that is easy to understand, but not so simple to use. If the problem is related to the size relationship between the elements before and after, you can try using monotone stack. There are also many problems that need to be converted to the problem of finding the next largest/smallest element, and then using monotone stack. This article has shared the monotonous stack definition, routine, typical actual combat case, if it is helpful, please like, look at, pay attention to support, this time certain.