单调栈和单调队列

Posted on | Post modified: | In |
Words count in article: 1.8k

单调栈

去除重复字母

  • 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
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
string removeDuplicateLetters(string s) {
        vector<int> cnt(26), appear(26);
        string stk;

        for (const char c : s) {
            ++ cnt[c - 'a'];
        }

        // 单调栈的思路，不过多了一些限制条件：出现的字符需要保存一个，于是有
        // 1. 当栈中已有该字符，则不能入栈
        // 2. 当能够弹出的字符在后面已经没有了，则不能弹出
        for (const char c : s) {
            if (!appear[c - 'a']) {   // 没在栈中的可以入栈，并且需要判断之前的字符是否需要出栈，而栈中已有的直接跳过 
                while (!stk.empty() && stk.back() > c) {
                    if (cnt[stk.back()- 'a'] == 0) break;
                    appear[stk.back() - 'a'] = 0;
                    stk.pop_back();
                }
                stk.push_back(c);
                appear[c - 'a'] = 1;
            }
            -- cnt[c - 'a'];  
        }
        
        return stk;
    }

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

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
// 暴力做法，直接搜索一个柱子两侧最高的柱，它的水平线一定是其中较矮的那个，这样每次左右分别搜索最高的柱子，一次搜索可以确定一个柱子上方的雨水量
// 搜索时需要包括本身（如果没有比自己高的那自己就是最高的）。
// class Solution{
// public:

// int trap(vector<int>& height)
// {
//     int ans = 0;
//     int size = height.size();
//     for (int i = 1; i < size - 1; i++) {
//         int max_left = 0, max_right = 0;
//         for (int j = i; j >= 0; j--) { //Search the left part for max bar size
//             max_left = max(max_left, height[j]);
//         }
//         for (int j = i; j < size; j++) { //Search the right part for max bar size
//             max_right = max(max_right, height[j]);
//         }
        
//         int t = min(max_left, max_right) - height[i];
//         ans += t;
//     }
//     return ans;
// }
// };


// // 动态规划：先正反两次遍历得到每个位置i的左右两端最大的数，则可以直接计算每个位置的水量
// class Solution {
// public:
//     int trap(vector<int>& h) {
//        int n = h.size();
//        int res = 0;

//        vector<int> left_max(n), right_max(n);
//        for (int t = -1, i = 0; i < n - 1; ++ i) {
//            if (t < h[i]) t = h[i];
//            left_max[i] = t; 
//        }

//        for (int t = -1, i = n - 1; i > 0; -- i) {
//            if (t < h[i]) t = h[i];
//            right_max[i] = t;
//        }

//        for (int i = 1; i < n - 1; ++ i) {
//            res += (min(right_max[i], left_max[i]) - h[i]);
//        }
//        return res;
//     }
// };

// 单调栈， 如果说暴力是按纵轴确认，单调栈就是按横轴确认（确定两个柱子之间有多宽的雨水量）。
// 雨水会出现在凹槽中，因此从左遍历只需要维护一个单调递减栈，就能保证左侧是凹的形状，当遇到不满足单调递减的柱时，计算左侧是否已有积水，和积水的宽度高度
// 并且由单调栈的性质，保存的一定是一个不增的序列。
// class Solution {
//     int stk[100000];
//     int tt = -1;
// public:
//     int trap(vector<int>& h) {
//         int n = h.size();
        
//         int res = 0;
//         for (int i = 0; i < n; ++ i) {
//             while (tt != -1 && h[stk[tt]] < h[i]) {
//                 int mid = stk[tt --];
//                 if (tt == -1) break;
//                 int l = stk[tt];
//                 res += (i - l - 1) * (min(h[i], h[l]) - h[mid]);
//             }
//             stk[++ tt] = i;
//         }
//         return res;
//     }
// };


// 双指针 ： 暴力法和动态规划都是需要一个柱子左右两侧最高的中较小的即可，那么可从两侧分别遍历，分别维护两侧最大的柱子，
// 在遍历的过程中，可以先计算较小端的水量，以左侧为例，它左侧的最大值已确定，而右侧最大值比它大，那么它的水量只与左侧最大值相关。
class Solution {
public:
    int trap(vector<int>& h) {
        int res = 0;
        int l = 0, r = h.size() - 1;
        int left_max = 0, right_max = 0;

        while (l <= r) {
            if (h[l] <= h[r]) {
                h[l] < left_max ? res += left_max - h[l] : left_max = h[l];
                ++ l;
            }else {
                h[r] < right_max ? res += right_max - h[r] : right_max = h[r];
                -- r;
            }
        }

        return res;
    }
};

132模式

132的结构中，2属于1,3之间，若要在1,3之间寻找2则需要维护多个区间，而1是最小的，如果可以维护一个尽量大的2，则可以方便的比较是否出现该结构。
则可从后往前遍历，同时使用单调栈来记录这样的性质。如果直接用单升栈是不能维护这样的性质的，因为我们需要一个尽量大的2，而不仅仅是一个单升的23性质。
因此可用单减栈，在遇到一个足够大的3时，2自然会弹出，而用一个变量记住弹出的最大的2即可。这样便维护了一个尽量大的2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool find132pattern(vector<int>& nums) {
    stack<int> st;
    int n = nums.size();
    int k = INT_MIN;

    for (int i = n - 1; i >= 0; -- i) {
        if (nums[i] < k) return true;
        while (st.size() && st.top() < nums[i]) {
            k = max(k, st.top());
            st.pop();
        }
        st.push(nums[i]);
    }
    return false;
}

单调队列

绝对差不超过限制的最长连续子数组

给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。

如果不存在满足条件的子数组，则返回 0 。

  • 区间的任意两个数的绝对值差只与区间最小和最大有关，本题的思路就是滑动窗口维护这个区间，其中区间性质的关键是要找到最大值和最小值，可分别用单减队列和单增队列来找最大和最小，右边界在进入时需要维护单调队列，然后通过两个单调队列求出绝对差来判断是否满足条件，不满足条件则需要右移左边界，左边界移动的时候判断是否有最大或最小值移出，直到满足条件为止，然后继续移动右边界直到结束。
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
int longestSubarray(vector<int>& nums, int limit) {
    int n = nums.size();
    deque<int> inc, dec;

    int l = 0, r = 0, maxlen = 1;

    while (r < n) {  // 右指针不断递增
        // 维护两个单调队列， 被弹出的都是不会影响绝对值之差的
        while (inc.size() && nums[inc.back()] > nums[r]) inc.pop_back();
        while (dec.size() && nums[dec.back()] < nums[r]) dec.pop_back();

        inc.push_back(r), dec.push_back(r);  // 加入队列

        // 维护左边界
        while (nums[dec.front()] - nums[inc.front()] > limit) {
            // 如果绝对差不满足，则右移左边界  直到满足条件，   同时判断左边界是否在单调队列中，有则弹出
            if (inc.size() && inc.front() == l) {
                inc.pop_front();
            }
            if (dec.size() && dec.front() == l) {
                dec.pop_front();
            }
            ++ l;
        }

        ++ r;
        maxlen = max(maxlen, r - l);
    }
    return maxlen;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int longestSubarray(vector<int>& nums, int limit) {
    multiset<int> s;
    int n = nums.size();
    int left = 0, right = 0;
    int ret = 0;
    while (right < n) {
        s.insert(nums[right]);
        while (*s.rbegin() - *s.begin() > limit) {
            s.erase(s.find(nums[left++]));
        }
        ret = max(ret, right - left + 1);
        right++;
    }
    return ret;
}