EI Madrigal's Space
0%

单调栈与单调队列

Posted on Edited on In
单调栈与单调队列

单调栈

对无重复元素的数组\([3,2,1,7,0,4,5,6]\)，求左侧和右侧第一个比nums[i]大（小）的元素索引：
对于greater，左侧的答案为\([-1,0,1,-1,3,3,3,3]\)，右侧的答案为\([3,3,3,-1,5,6,7,-1]\)；
对于smaller，左侧的答案为\([-1,-1,-1,2,-1,4,5,6]\)，右侧的答案为\([1,2,4,4,-1,-1,-1,-1]\)。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 数组中无重复值 first存左侧索引 second存右侧索引
vector<pair<int, int>> monotonousStack(vector<int>& nums) {
    stack<int> s;  // store index
    vector<pair<int, int>> ans(nums.size());  // return index
    
    for (int i = 0; i < nums.size(); ++i) {
        // 求smaller. 若需greater, 改为 nums[i] > nums[s.top()]
        while (!s.empty() && nums[i] < nums[s.top()]) {
            int idx = s.top(); s.pop();
            ans[idx].first = s.empty() ? -1 : s.top();
            ans[idx].second = i;
        }
        s.push(i);
    }
    while (!s.empty()) {
        int idx = s.top(); s.pop();
        ans[idx].first = s.empty() ? -1 : s.top();
        ans[idx].second = -1;
    }
    return ans;
}

如果数组中存在重复元素，比如\([3,2,3,4,4,3,1]\)：
对于greater，左侧的答案为\([-1,0,-1,-1,-1,4,5]\)，右侧的答案为\([3,2,3,-1,-1,-1,-1]\)；
对于smaller，左侧的答案为\([-1,-1,1,2,2,1,-1]\)，右侧的答案为\([1,6,6,5,5,6,-1]\)

对于有重复元素，如果直接使用上述无重元素的代码，有以下情况：

  1. nums[i] < nums[s.top()]：左侧变为\([-1,-1,1,2,3,2,-1]\)，即左侧第一个小于等于nums[i]的元素位置，不再是严格小于；右侧不变，仍然严格小于
  2. nums[i] <= nums[s.top()]：左侧不变，仍然严格小于；右侧变为\([1,6,5,4,5,6,-1]\)，即右侧第一个小于等于nums[i]的元素位置，不再是严格小于
  3. nums[i] > nums[s.top()]：左侧变为\([-1,0,0,-1,3,4,5]\)，即左侧第一个大于等于nums[i]的元素位置，不再是严格大于；右侧不变，仍然严格大于
  4. nums[i] >= nums[s.top()]：左侧不变，仍然严格大于；右侧变为\([2,2,3,4,-1,-1,-1]\)，即右侧第一个大于等于nums[i]的元素位置，不再是严格大于
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
// 左边和右边第一个比nums[i]小(大)的元素索引 栈自底向上从小到大(从大到小)

// 数组中无重复值 first存左侧索引 second存右侧索引
vector<pair<int, int>> monotonousStack(vector<int>& nums) {
    stack<int> s;  // store index
    vector<pair<int, int>> ans(nums.size());  // return index
    
    for (int i = 0; i < nums.size(); ++i) {
        // 求smaller. 若需greater, 改为 nums[i] > nums[s.top()]
        while (!s.empty() && nums[i] < nums[s.top()]) {
            int idx = s.top(); s.pop();
            ans[idx].first = s.empty() ? -1 : s.top();
            ans[idx].second = i;
        }
        s.push(i);
    }
    while (!s.empty()) {
        int idx = s.top(); s.pop();
        ans[idx].first = s.empty() ? -1 : s.top();
        ans[idx].second = -1;
    }
    return ans;
} 

// 数组中有重复值, 右侧可以沿用上面代码, 左侧不可
vector<pair<int, int>> monotonousStackRepeat(vector<int>& nums) {
    stack<vector<int>> s;  // store index, same number's idx stores together
    vector<pair<int, int>> ans(nums.size());  // return index
    
    for (int i = 0; i < nums.size(); ++i) {
        // 求smaller. 若需greater, 改为 nums[i] > nums[s.top()]
        while (!s.empty() && nums[i] < nums[s.top()[0]]) {
            vector<int> popIdx = s.top(); s.pop();
            int leftSmallIdx = s.empty() ? -1 : s.top()[s.top().size() - 1];
            for (int idx : popIdx) {
                ans[idx].first = leftSmallIdx;
                ans[idx].second = i;
            }
        }
        if (!s.empty() && nums[i] == nums[s.top()[0]]) {
            s.top().emplace_back(i);
        }
        else {
            s.push({i});
        }
    }
    while (!s.empty()) {
        vector<int> popIdx = s.top(); s.pop();
        int leftSmallIdx = s.empty() ? -1 : s.top()[s.top().size() - 1];
        for (int idx : popIdx) {
            ans[idx].first = leftSmallIdx;
            ans[idx].second = -1;
        }
    }
    return ans;
}

单调队列

单调队列主要用来解决: 数组中所有长度为\(k\)的区间最值问题.

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 求所有区间长度为k的最大值
vector<int> monotonousQueue(vector<int>& nums, int k) {
    vector<int> res;
    deque<int> q;  // store index, front is the largest

    for (int i = 0; i < nums.size(); ++i) {
        if (!q.empty() && i - q.front() >= k) {
            q.pop_front();
        }
        while (!q.empty() && nums[i] > nums[q.back()]) {  // 改为 < 即求区间最小
            q.pop_back();
        }
        q.push_back(i);
        if (i >= k - 1) {
            res.push_back(nums[q.front()]);
        }
    }
    return res;
}

Ref

1:34:00开始