单调栈的性质和使用场景

单调栈

简介

单调栈即需要保证入栈的元素是保持递增或者递减的。如果有违反递增或者递减的原则，那么就需要通过弹出栈的方式来保持单调栈的性质。
单调栈常被用来解决滑动窗口中元素最大值和最小值的问题。

实践

剑指 Offer 59 - I. 滑动窗口的最大值添加链接描述

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

思路

观察窗口的滑动过程：
当窗口区间为 $\left[i,j\right]$ ,对应的窗口中的值的集合为 { n u m i , n u m i + 1 , . . . n u m j } \left \{ num_i,num_{i+1},... num_j \right \} {numi​,numi+1​,...numj​}, 当窗口从左向右移动一格，那么会舍弃掉$nu{m}_i$,滑动窗口内增加一个值$nu{m}_{j+1}$,如果集合 { n u m i , n u m i + 1 , . . . n u m j } \left \{ num_i,num_{i+1},... num_j \right \} {numi​,numi+1​,...numj​}中只要有值比$nu{m}_{j+1}$小，那么只要往右边滑动，最大值肯定不是集合中比$nu{m}_{j+1}$小的值，因此可以将该集合中比$nu{m}_{j+1}$小的值舍弃，照此思路，构建单调递减栈。

代码

class Solution {
    public:
    class MonotonicStack{
        deque<long long > deq;
        int max = INT_MIN;
        vector<int> vec;
    public:
        MonotonicStack(vector<int> num, int k){
            vec = num;
            for(int i = 0; i < k && i < num.size();++i)
            {
                if(num[i] > max){
                    max = num[i];
                    deq.clear();
                    deq.push_back(num[i]);
                }else{
                    while(deq[deq.size() -1] < num[i]) {
                        deq.pop_back();
                    }
                    deq.push_back(num[i]);
                }
            }
        }

    public :
        void push(int i) {
            if(vec[i] > max){
                max = vec[i];
                deq.clear();
                deq.push_back(vec[i]);
            } else {
                while(deq.size() > 0 && deq[deq.size() -1] < vec[i]) {
                    deq.pop_back();
                }
                deq.push_back(vec[i]);
            }
        }

        void pop(int start) {
            if(deq.size() > 0 && vec[start] == max) {
                max = deq.size() > 1 ? deq[1] : INT_MIN;
                deq.pop_front();
            }
        }

        int getMaxNum(){
            return this->max;
        }
    };

public :
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(k <= 0){
            return vector<int> {};
        }

        vector<int> vec;
        MonotonicStack* monotonicStack =  new MonotonicStack(nums, k);
        if(k >= nums.size()){
            vec.push_back(monotonicStack->getMaxNum());
        } else {
            for(int i = k; i < nums.size(); ++i) {
                vec.push_back(monotonicStack -> getMaxNum());
                monotonicStack -> pop(i-k);
                monotonicStack ->push(i);
            }
            vec.push_back(monotonicStack -> getMaxNum());
        }
        delete monotonicStack;
        monotonicStack = nullptr;
        return vec;
    }
}; 
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

代码理解

构造一个内部类，该类使用双向队列deque保存滑动窗口单调栈的值，在MonotonicStack的构造函数中初始化单调递减栈，然后通过循环调用MonotonicStack的pop和push函数，更新滑动窗口的$max$值。