The Thought and Application of Monotone Stack

Posted on Edited on In Waline:

Recently, I have seen the use of monotonic stack in several different situations. This time, I will systematically summarize the idea of monotonic stack and its use in various situations.

Stack is a very simple data structure, with a logical order of first in and last out, which meets the characteristics of certain problems, such as function call stack.

A monotonic stack is actually a stack, but with some clever logic, every time a new element is added to the stack, the elements in the stack remain in order (monotonically increasing or monotonically decreasing).

The monotonic stack is not very versatile and only deals with a typical problem called the Next Greater (Or Smaller) Element.

The use of monotone stack is also divided into situations:

  • Divided into two categories from finding the nearest larger or smaller element.

  • There are three cases from whether to find the next nearest larger (or smaller) element from the left, right, or both sides.

So there are 6 cases in total.

The nearest larger element on the right

Let’s first look at the simplest case, from finding the nearest element to the right of the element that is larger than it, this example on leetcode is called: https://leetcode-cn.com/problems/next-greater-element-i

For example, if you enter an array nums = [2, 1, 2, 4, 3], you return the array [4, 2, 4, -1, -1].

Explanation: The number larger than 2 after the first 2 is 4; the number larger than 1 after 1 is 2; the number larger than 2 after the second 2 is 4; there is no number larger than 4 after 4, fill in -1; There is no number larger than 3 after 3, fill in -1.

The brute force solution to this problem is easy to think of, that is, scan behind each element to find the first larger element. But the time complexity of the brute force solution is’ O (n ^ 2) '.

This question can be thought of abstractly like this: imagine the elements of an array as people standing side by side, and the size of the elements as the height of an adult. These people stand in a column facing you, how to find the Next Greater Number of element “2”? Very simple, if you can see element “2”, then the first person visible behind him is the Next Greater Number of “2”, because the element smaller than “2” is not tall enough, it is blocked by “2”, and the first one exposed is the answer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> nextGreaterElement(vector<int>& nums) {
    Vector < int > res (nums.size ()); // array of answers
    stack<int> s;
    //put it in the stack upside down
    for (int i = nums.size() - 1; i >= 0; i--) {
        //Determine the height
        while (!s.empty() && s.top() <= nums[i]) {
            //The short one starts to move, it's blocked anyway.........
            s.pop();
        }
        // nums[i] 身后的 next great number
        res[i] = s.empty() ? -1 : s.top();
        // 
        s.push(nums[i]);
    }
    return res;
}

This is the template for solving the problem of monotonic queues. The rest of the cases are modified from this template. The for loop scans elements from back to front, because we use the stack structure to put them onto the stack backwards, which is actually going out of the stack backwards. The while loop excludes the elements between two “taller” elements, because their existence is meaningless and there is a “taller” element in front, so they cannot be used as the Next Great Number of incoming elements

The nearest smaller element on the right

Compared with the previous case, this case is that the judgment condition of the while loop is modified from less than or equal to greater than or equal to.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> nextGreaterElement(vector<int>& nums) {
    Vector < int > res (nums.size ()); // array of answers
    stack<int> s;
    //put it in the stack upside down
    for (int i = nums.size() - 1; i >= 0; i--) {
        //Determine the height
        while (!s.empty() && s.top() >= nums[i]) {
            //The tall one gets up and blocks me.........
            s.pop();
        }
        // nums[i] 身后的 next small number
        res[i] = s.empty() ? -1 : s.top();
        // 
        s.push(nums[i]);
    }
    return res;
}

Left

The nearest larger element on the left

The for loop starts on the left side compared to the right

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> nextGreaterElement(vector<int>& nums) {
    Vector < int > res (nums.size ()); // array of answers
    stack<int> s;
    //put it in the stack upside down
    for (int i = 0; i < nums.size(); i++) {
        //Determine the height
        while (!s.empty() && s.top() <= nums[i]) {
            //The short one starts to move, it's blocked anyway.........
            s.pop();
        }
        // nums[i] 身后的 next great number
        res[i] = s.empty() ? -1 : s.top();
        // 
        s.push(nums[i]);
    }
    return res;
}

The nearest smaller element on the left

Compared with the previous case, this case is that the judgment condition of the while loop is modified from less than or equal to greater than or equal to.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> nextGreaterElement(vector<int>& nums) {
    Vector < int > res (nums.size ()); // array of answers
    stack<int> s;
    //put it in the stack upside down
    for (int i = 0; i < nums.size(); i++) {
        //Determine the height
        while (!s.empty() && s.top() >= nums[i]) {
            //The tall one gets up and blocks me.........
            s.pop();
        }
        // nums[i] 身后的 next small number
        res[i] = s.empty() ? -1 : s.top();
        // 
        s.push(nums[i]);
    }
    return res;
}

Both sides

You can see this example: https://leetcode-cn.com/problems/next-greater-element-ii/

The same is Next Greater Number. Now suppose the array given to you is a ring. How to deal with it? The 503 question of the force buckle “Next Greater Element II” is this question:

For example, if you enter an array ‘[2, 1, 2, 4, 3]’, you return the array ‘[4, 2, 4, -1, 4]’. With the ring property, ** the last element 3 goes around and finds the element 4 ** larger than itself.

Generally, the ring effect is obtained by modulo (remainder) of the% operator:

1
2
3
4
5
6
int[] arr = {1,2,3,4,5};
int n = arr.length, index = 0;
while (true) {
    print(arr[index % n]);
    index++;
}

This problem must still use a monotone stack solution template, but the difficulty lies in, for example, the input is’ [2, 1, 2, 4, 3] ', for the last element 3, how to find element 4 as Next Greater Number.

** For this requirement, the common routine is to double the length of the array **:

In this way, element 3 finds element 4 as the Next Greater Number, and all other elements can be calculated correctly.

With this idea, the simplest way to implement it is of course to construct this double-length array and then apply the algorithm template. However, instead of constructing a new array, we can use the loop array technique to simulate the effect of doubling the length of the array.

Just look at the code directly:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> nextGreaterElements(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n);
    stack<int> s;
    //Pretend that the length of this array has doubled. At this time, it is the same from left to right or right to left.
    for (int i = 2 * n - 1; i >= 0; i--) {
        //Indexing requires modulus, others are the same as templates
        while (!s.empty() && s.top() <= nums[i % n])
            s.pop();
        res[i % n] = s.empty() ? -1 : s.top();
        s.push(nums[i % n]);
    }
    return res;
}

In this way, the problem of ring arrays can be cleverly solved with time complexity O (N).

Comprehensive application

After reading the above description, you can take a look at the topic of this comprehensive application; https://leetcode-cn.com/problems/sum-of-subarray-ranges/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
typedef struct {
    int * stBuff;
    int stSize;
    int stTop;
} Stack;

void initStack(Stack * obj, int stSize) {
    obj->stBuff = (int *)malloc(sizeof(int) * stSize);
    obj->stSize = stSize;
    obj->stTop = 0;
}

static inline bool pushStack(Stack * obj, int val) {
    if (obj->stTop  obj->stSize) {
        return false;
    }
    obj->stBuff[obj->stTop++] = val;
    return true;
}

static inline int popStack(Stack * obj) {
    if (obj->stTop  0) {
        return -1;
    }
    int res =  obj->stBuff[obj->stTop - 1];
    obj->stTop--;
    return res;
}


static inline bool isEmptyStack(const Stack * obj) {
    return obj->stTop  0;
}

static inline int topStack(const Stack * obj) {
    if (obj->stTop  0) {
        return -1;
    }
    return obj->stBuff[obj->stTop - 1]; 
}

static inline bool clearStack(Stack * obj) {
    obj->stTop = 0;
    return true;
}

static inline void freeStack(Stack * obj) {
    free(obj->stBuff);
}

long long subArrayRanges(int* nums, int numsSize){
    int * minLeft = (int *)malloc(sizeof(int) * numsSize);
    int * minRight = (int *)malloc(sizeof(int) * numsSize);
    int * maxLeft = (int *)malloc(sizeof(int) * numsSize);
    int * maxRight = (int *)malloc(sizeof(int) * numsSize);
    Stack minStack, maxStack;
    initStack(&minStack, numsSize);
    initStack(&maxStack, numsSize);
    for (int i = 0; i < numsSize; i++) {
        //if nums [maxStack.top () ]  nums[i], 那么根据定义，
        //nums [maxStack.top () ] is logically less than nums [i] because maxStack.top () < i, and I'm looking for logically smaller ones than me, so it doesn't need to be filtered out
        while (!isEmptyStack(&minStack) && nums[topStack(&minStack)] > nums[i]) {
            popStack(&minStack);
        }
        minLeft[i] = isEmptyStack(&minStack) ? -1 : topStack(&minStack);
        pushStack(&minStack, i);
        
        //if nums [maxStack.top () ]  nums[i], 那么根据定义，
        //nums [maxStack.top () ] is logically less than nums [i], because maxStack.top () < i, so it needs to be filtered out
        while (!isEmptyStack(&maxStack) && nums[topStack(&maxStack)] <= nums[i]) { 
            popStack(&maxStack);
        }
        maxLeft[i] = isEmptyStack(&maxStack) ? -1 : topStack(&maxStack);
        pushStack(&maxStack, i);
    }
    clearStack(&minStack);
    clearStack(&maxStack);
    for (int i = numsSize - 1; i >= 0; i--) {
        //if nums [minStack.top () ]  nums[i], 那么根据定义，
        //nums [minStack.top () ] is logically greater than nums [i], because minStack.top () > i, so it needs to be sifted out
        while (!isEmptyStack(&minStack) && nums[topStack(&minStack)] >= nums[i]) { 
            popStack(&minStack);
        }
        minRight[i] = isEmptyStack(&minStack) ? numsSize : topStack(&minStack);
        pushStack(&minStack, i);

        //if nums [minStack.top () ]  nums[i], 那么根据定义，
        //nums [minStack.top () ] is logically greater than nums [i], because minStack.top () > i, so there is no need to sift out
        while (!isEmptyStack(&maxStack) && nums[topStack(&maxStack)] < nums[i]) { 
            popStack(&maxStack);
        }
        maxRight[i] = isEmptyStack(&maxStack) ? numsSize : topStack(&maxStack);
        pushStack(&maxStack, i);
    }
    freeStack(&minStack);
    freeStack(&maxStack);

    long long sumMax = 0, sumMin = 0;
    for (int i = 0; i < numsSize; i++) {
        sumMax += (long long)(maxRight[i] - i) * (i - maxLeft[i]) * nums[i];
        sumMin += (long long)(minRight[i] - i) * (i - minLeft[i]) * nums[i];
    }
    
    return sumMax - sumMin;
}