Monotonic stack Introduction

A monotone stack is a data structure that is easy to understand, but not so simple to use. A monotone stack is a stack in which the size of the elements in the stack meets a certain monotonicity according to their position in the stack. So when do we use this monotone stack, how do we use the monotone stack. Let’s look at some examples.

First, let’s share a very simple question encountered in the Google Interview.

An appetizer

So it says, given an array, return an array of the same size. The value of the i-th position of the returned array should be at least how many steps to the right of the i-th element of the original array before it encounters an element larger than itself (if there is no element larger than itself later, or if it is already the last element, put -1 in the corresponding position of the returned array).

A simple example:

Input: 5,3,1,2,4

return: -1 3 1 1 -1

Explaination: For the 0th number 5, there is no larger number after that, so it is -1, for the 1st number 3, it takes 3 steps to reach 4 (the first element larger than 3), for both the 2nd and 3rd numbers, it takes only 1 step to encounter the element larger than itself. For the last number, 4, since there are no more elements, it’s -1.

The result of violence is O(n^2) time, for example, for a monotonically decreasing array, going to the end of the array every time. So what do we do with monotone stacks? Let’s start with the code: Note that the monotonic stack record stores the subscript of the array

vector<int> nextExceed(vector<int> &input) { vector<int> result (input.size(), -1); stack<int> monoStack; for(int i = 0; i < input.size(); ++i) { while(! monoStack.empty() && input[monoStack.top()] < input[i]) { result[monoStack.top()] = i - monoStack.top(); monoStack.pop(); } monoStack.push(i); } return result; }Copy the code

Java

public static int[] nextExceed(int[] input) { int[] result = new int[input.length]; Arrays.*fill*(result, -1); Deque<Integer> stack = new ArrayDeque<>(input.length); for (int i = 0; i < input.length; i++) { while (! stack.isEmpty() && input[i] > input[stack.peek()]) { int top = stack.pop(); result[top] = i - top; } stack.push(i); } return result; }Copy the code

We maintain a monotonically decreasing stack that holds each index of the original array. We encounter a “large number” whenever we encounter a number greater than the number corresponding to the current top of the stack (input[monostack.top ()]). 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 that corresponds to 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 its next greater Element, and we update the value of the corresponding position in the return array. If an element never exits the stack, then there is no next Greater Element and we do not need to update the return array.

In this example, there is only one push and one push for each element, so the time complexity is O(n).

Properties of monotone stack:

1. Monotone stack is a stack in which elements increase or decrease monotonously. Monotone stack can only operate at the top of the stack.

2. Before the element is added to the stack, all elements that break the monotony of the stack are deleted at the top of the stack

3. Use monotone stack to find the element traversing the first smaller element to the left, or find the element traversing the first larger element to the left.

(Original link)

Other topics:

Look at the solution of the time focus on monotonous stack solution

The largest rectangle in the bar chart

Leetcode-cn.com/problems/la…

#85 Maximum rectangle area

Leetcode-cn.com/problems/ma…

One instance

#496 Next larger element I

#503 Next larger element II

Daily temperature

# 42 after the rain

#901 Stock price span

#239 Maximum sliding window

#962 Maximum width slope

Extension:

# 363

Leetcode-cn.com/problems/ma…