单调栈

发表于 | 分类于 | 浏览 次

什么是单调栈？

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

/**
 * 对于不含重复元素的数组求其中每个元素左边和右边小于该元素且距离该元素最近的位置
 */
vector<vector<int>> getNearLessNoRepeat(vector<int> &arr) {
    vector<vector<int>> res(arr.size(), vector<int>(2, -1));
    stack<int> s1;
    for (int i = 0; i < arr.size(); ++i) {
        while (!s1.empty() && arr[s1.top()] > arr[i]) {
            int popIndex = s1.top();
            s1.pop();
            int left = s1.empty() ? -1 : s1.top();
            res[popIndex][0] = left;
            res[popIndex][1] = i;
        }
        s1.push(i);
    }
    while (!s1.empty()) {
        int popIndex = s1.top();
        s1.pop();
        int left = s1.empty() ? -1 : s1.top();
        res[popIndex][0] = left;
        res[popIndex][1] = -1;
    }
    return res;
}

/**
 * 对于含重复元素的数组求其中每个元素左边和右边小于该元素且距离该元素最近的位置
 * 方法１：把所有相等元素放到一个vector中
 */
vector<vector<int>> getNearLess(vector<int> &arr) {
    vector<vector<int>> res(arr.size(), vector<int>(2, -1));
    stack<vector<int>> s1;
    for (int i = 0; i < arr.size(); ++i) {
        while (!s1.empty() && arr[s1.top()[0]] > arr[i]) {
            vector<int> popIs = s1.top();
            s1.pop();

            int left = s1.empty() ? -1 : s1.top()[s1.top().size() - 1];
            for (int popi : popIs) {
                res[popi][0] = left;
                res[popi][1] = i;
            }
        }
        if (!s1.empty() && arr[s1.top()[s1.top().size() - 1]] == arr[i]) {
            s1.top().push_back(i);
        } else {
            vector<int> tmp{i};
            s1.push(tmp);
        }
    }

    while (!s1.empty()) {
        vector<int> popIs = s1.top();
        s1.pop();
        int left = s1.empty() ? -1 : s1.top()[s1.top().size() - 1];
        for (int popi: popIs) {
            res[popi][0] = left;
            res[popi][1] = -1;
        }
    }
    return res;
}

/**
 * 对于含重复元素的数组求其中每个元素左边和右边小于该元素且距离该元素最近的位置
 * 方法2：对于每个元素从栈中退出时才统计与其相等的元素
 */
vector<vector<int>> getNearLess2(vector<int> &arr) {
    vector<vector<int>> res(arr.size(), vector<int>(2, -1));
    stack<int> s1;
    for (int i = 0; i < arr.size(); ++i) {
        int right = i;
        while (!s1.empty() && arr[s1.top()] > arr[i]) {
            int idx = s1.top();
            vector<int> tmp{idx};
            while (!s1.empty() && arr[s1.top()] == arr[idx]) {
                tmp.push_back(s1.top());
                s1.pop();
            }
            int left = s1.empty() ? -1 : s1.top();
            for (auto index : tmp) {
                res[index][0] = left;
                res[index][1] = right;
            }
        }
        s1.push(i);
    }
    int right = -1;
    while (!s1.empty()) {
        int idx = s1.top();
        vector<int> tmp{idx};
        while (!s1.empty() && arr[idx] == arr[s1.top()]) {
            tmp.push_back(s1.top());
            s1.pop();
        }
        int left = s1.empty() ? -1 : s1.top();
        for (auto index:tmp) {
            res[index][0] = left;
            res[index][1] = right;
        }
    }
    return res;
}

int main() {
    vector<int> arr{3, 1, 3, 4, 3, 5, 3, 2, 2};
    vector<vector<int>> res1 = getNearLess(arr);
    vector<vector<int>> res2 = getNearLess2(arr);
    for (int i = 0; i < arr.size(); ++i) {
        cout << arr[i] << " " << res1[i][0] << " " << res1[i][1] << endl;
    }
    cout << endl;

    for (int i = 0; i < arr.size(); ++i) {
        cout << arr[i] << " " << res2[i][0] << " " << res2[i][1] << endl;
    }
    cout << endl;
    return 0;
}

单调栈的应用