单调栈的思想与应用

发表于 更新于 分类于 Waline：
单调栈的思想与应用

最近看到了几种不同情况下的单调栈的使用，这次就系统性地总结一下单调栈的思想以及各种不同情况下的使用。

栈（stack）是很简单的一种数据结构，先进后出的逻辑顺序，符合某些问题的特点，比如说函数调用栈。

单调栈实际上就是栈，只是利用了一些巧妙的逻辑，使得每次新元素入栈后，栈内的元素都保持有序（单调递增或单调递减）。

单调栈用途不太广泛，只处理一种典型的问题，叫做 Next Greater（Or Smaller） Element。

而单调栈的使用也是分情况的：

  • 从找的是最近的更大的还是更小的元素分为两类。

  • 从是否是是从左侧，右侧还是两侧找下一个最近的更大（或更小）的元素分为三种情况。

所以一共加起来是6种情况。

右侧

右侧最近的更大的元素

我们首先来看最简单的一种情况，从找出元素右侧最近的一个比他更大的元素，这个在leetcode上的例题为：https://leetcode-cn.com/problems/next-greater-element-i

比如说，输入一个数组 nums = [2,1,2,4,3]，你返回数组 [4,2,4,-1,-1]。

解释：第一个 2 后面比 2 大的数是 4; 1 后面比 1 大的数是 2；第二个 2 后面比 2 大的数是 4; 4 后面没有比 4 大的数，填 -1；3 后面没有比 3 大的数，填 -1。

这道题的暴力解法很好想到，就是对每个元素后面都进行扫描，找到第一个更大的元素就行了。但是暴力解法的时间复杂度是 O(n^2)。

这个问题可以这样抽象思考：把数组的元素想象成并列站立的人，元素大小想象成人的身高。这些人面对你站成一列，如何求元素「2」的 Next Greater Number 呢？很简单，如果能够看到元素「2」，那么他后面可见的第一个人就是「2」的 Next Greater Number，因为比「2」小的元素身高不够，都被「2」挡住了，第一个露出来的就是答案。

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()); // 存放答案的数组
    stack<int> s;
    // 倒着往栈里放
    for (int i = nums.size() - 1; i >= 0; i--) {
        // 判定个子高矮
        while (!s.empty() && s.top() <= nums[i]) {
            // 矮个起开，反正也被挡着了。。。
            s.pop();
        }
        // nums[i] 身后的 next great number
        res[i] = s.empty() ? -1 : s.top();
        // 
        s.push(nums[i]);
    }
    return res;
}

这就是单调队列解决问题的模板，其他的情况都是从这个模版修改的。for 循环要从后往前扫描元素，因为我们借助的是栈的结构，倒着入栈，其实是正着出栈。while 循环是把两个「个子高」元素之间的元素排除，因为他们的存在没有意义，前面挡着个「更高」的元素，所以他们不可能被作为后续进来的元素的 Next Great Number 了

右侧最近的更小的元素

这种情况和上一种情况相比，就是while循环的判断条件修改了从小于等于变为大于等于。

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()); // 存放答案的数组
    stack<int> s;
    // 倒着往栈里放
    for (int i = nums.size() - 1; i >= 0; i--) {
        // 判定个子高矮
        while (!s.empty() && s.top() >= nums[i]) {
            // 高个起开，挡着我。。。
            s.pop();
        }
        // nums[i] 身后的 next small number
        res[i] = s.empty() ? -1 : s.top();
        // 
        s.push(nums[i]);
    }
    return res;
}

左侧

左侧最近的更大的元素

与右侧相比，for循环是从左侧开始

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()); // 存放答案的数组
    stack<int> s;
    // 倒着往栈里放
    for (int i = 0; i < nums.size(); i++) {
        // 判定个子高矮
        while (!s.empty() && s.top() <= nums[i]) {
            // 矮个起开，反正也被挡着了。。。
            s.pop();
        }
        // nums[i] 身后的 next great number
        res[i] = s.empty() ? -1 : s.top();
        // 
        s.push(nums[i]);
    }
    return res;
}

左侧最近的更小的元素

这种情况和上一种情况相比，就是while循环的判断条件修改了从小于等于变为大于等于。

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()); // 存放答案的数组
    stack<int> s;
    // 倒着往栈里放
    for (int i = 0; i < nums.size(); i++) {
        // 判定个子高矮
        while (!s.empty() && s.top() >= nums[i]) {
            // 高个起开，挡着我。。。
            s.pop();
        }
        // nums[i] 身后的 next small number
        res[i] = s.empty() ? -1 : s.top();
        // 
        s.push(nums[i]);
    }
    return res;
}

两侧

这个例题可以看：https://leetcode-cn.com/problems/next-greater-element-ii/

同样是 Next Greater Number，现在假设给你的数组是个环形的，如何处理？力扣第 503 题「下一个更大元素 II」就是这个问题：

比如输入一个数组 [2,1,2,4,3]，你返回数组 [4,2,4,-1,4]。拥有了环形属性，最后一个元素 3 绕了一圈后找到了比自己大的元素 4。

一般是通过 % 运算符求模（余数），来获得环形特效：

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++;
}

这个问题肯定还是要用单调栈的解题模板，但难点在于，比如输入是 [2,1,2,4,3]，对于最后一个元素 3，如何找到元素 4 作为 Next Greater Number。

对于这种需求，常用套路就是将数组长度翻倍：

这样，元素 3 就可以找到元素 4 作为 Next Greater Number 了，而且其他的元素都可以被正确地计算。

有了思路，最简单的实现方式当然可以把这个双倍长度的数组构造出来，然后套用算法模板。但是，我们可以不用构造新数组，而是利用循环数组的技巧来模拟数组长度翻倍的效果。

直接看代码吧：

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;
    // 假装这个数组长度翻倍了，这个时候从左到右还是从右到左都一样了
    for (int i = 2 * n - 1; i >= 0; i--) {
        // 索引要求模，其他的和模板一样
        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;
}

这样，就可以巧妙解决环形数组的问题，时间复杂度 O(N)

综合应用

看完上面的说明，可以看看这道综合应用的题目；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++) {
        // 如果 nums[maxStack.top()] == nums[i], 那么根据定义，
        // nums[maxStack.top()] 逻辑上小于 nums[i]，因为 maxStack.top() < i，而我找的就是逻辑上比我小的,所以说不需要被筛掉
        while (!isEmptyStack(&minStack) && nums[topStack(&minStack)] > nums[i]) {
            popStack(&minStack);
        }
        minLeft[i] = isEmptyStack(&minStack) ? -1 : topStack(&minStack);
        pushStack(&minStack, i);
        
        // 如果 nums[maxStack.top()] == nums[i], 那么根据定义，
        // nums[maxStack.top()] 逻辑上小于 nums[i]，因为 maxStack.top() < i，所以说需要筛掉
        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--) {
        // 如果 nums[minStack.top()] == nums[i], 那么根据定义，
        // nums[minStack.top()] 逻辑上大于 nums[i]，因为 minStack.top() > i，所以说需要筛去
        while (!isEmptyStack(&minStack) && nums[topStack(&minStack)] >= nums[i]) { 
            popStack(&minStack);
        }
        minRight[i] = isEmptyStack(&minStack) ? numsSize : topStack(&minStack);
        pushStack(&minStack, i);

        // 如果 nums[minStack.top()] == nums[i], 那么根据定义，
        // nums[minStack.top()] 逻辑上大于 nums[i]，因为 minStack.top() > i，所以不需要筛去
        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;
}