栈与队列力扣题目汇总

Category： DSA

写在前面

栈入门

主要用于深度优先搜索, 模拟递归过程, 以及一些特定解法的题目(例如单调栈, 括号匹配, 逆波兰表达式求值等),

基本实现

通过C风格数组很容易实现栈(但是固定了长度), 在C++STL中也有实现(通过deque), 不过基本的栈操作还是要用数组来完成, 要了解每一个API的实现过程.

基本题目

// 💩一样的代码
class Solution {
public:
    bool isValid(string s) {
        if (s.size() & 1) return false;
        stack<char> st;
        for (auto c : s) {
            if (c == '(' || c == '[' || c == '{')
                st.push(c);
            else if (st.empty())
                return false;
            else if (c == ')')
                if (st.top() == '(')
                    st.pop();
                else
                    return false;
            else if (c == ']')
                if (st.top() == '[')
                    st.pop();
                else
                    return false;
            else if (c == '}')
                if (st.top() == '{')
                    st.pop();
                else
                    return false;
        }
        return st.empty();
    }
};
// 官方的代码:
class Solution {
public:
    bool isValid(string s) {
        if (s.size() & 1) return false;
        stack<char> st;
        unordered_map<char, char> pairs{
            {')', '('},
            {']', '['},
            {'}', '{'},
        };
        for (auto c : s) {
            if (pairs.find(c) != pairs.end()) {
                if (st.empty() || st.top() != pairs[c]) return false;
                st.pop();
            } else
                st.push(c);
        }
        return st.empty();
    }
};

921. 使括号有效的最少添加;(其中也蕴含了贪心的思想, 每次就近匹配括号) cpp class Solution { public: int minAddToMakeValid(string s) { stack<char> st; for (char c : s) { if (c == ')' && !st.empty() && st.top() == '(') st.pop(); else st.emplace(c); } return st.size(); } };

队列入门

主要用于广度优先搜索, 以及一些需要后进先出的情况.

栈进阶

最小栈

155. 最小栈 - 力扣（LeetCode）;

STL: 用两个栈来模拟.

class MinStack {
    stack<int> s1, m1;

public:
    MinStack() { m1.emplace(INT_MAX); }

    void push(int val) {
        s1.emplace(val);
        m1.emplace(min(getMin(), val));
    }

    void pop() { s1.pop(), m1.pop(); }

    int top() { return s1.top(); }

    int getMin() { return m1.top(); }
};

数组模拟:

class MinStack {
    vector<int> s1, m1;

public:
    MinStack() { m1.emplace_back(INT_MAX); }

    void push(int val) {
        s1.emplace_back(val);
        m1.emplace_back(min(getMin(), val));
    }

    void pop() { s1.pop_back(), m1.pop_back(); }

    int top() { return s1.back(); }

    int getMin() { return m1.back(); }
};

$\bigstar$单一栈实现: 通过数组差值来做:

class MinStack {
    stack<long> st; // 里面存的是数之间的差值
    long min_val;   // min_val每次只存最小值
public:
    MinStack() : st(), min_val() {}

    void push(int val) {
        if (st.empty())
            st.emplace(0), min_val = val;
        else {
            long diff = val - min_val;
            st.emplace(diff);
            if (diff < 0) min_val = val; // 更新 min_val
        }
    }

    void pop() {
        long diff = st.top();
        st.pop();
        if (diff < 0) min_val -= diff; // 更新 min_val
    }

    int top() { return st.top() < 0 ? min_val : st.top() + min_val; }

    int getMin() { return min_val; }
};

数组模拟, 几乎双百.

class MinStack {
    vector<long> st; // 存放当前入栈的值和已记录的最小值的差
    long min_val;    // 已记录的最小值

public:
    MinStack() : st(), min_val() {}

    void push(int val) {
        if (st.empty())
            st.emplace_back(0), min_val = val; // 首元素(差值)为0
        else {
            st.emplace_back(val - min_val);
            if (st.back() < 0) min_val = val; // 差值为负值, 更新最小值
        }
    }

    void pop() {
        auto tmp{st.back()};
        if (tmp < 0) min_val -= tmp; // 最小值弹出, 更新
        st.pop_back();
    }

    int top() { return st.back() > 0 ? min_val + st.back() : min_val; }

    int getMin() { return min_val; }
};

栈内排序

面试题 03.05. 栈排序 - 力扣（LeetCode）;

class SortedStack {
    stack<int> st;

public:
    SortedStack() {}

    void push(int val) {
        function<void(int)> f = [&](int x) {
            if (st.empty() || st.top() >= x)
                st.emplace(x);
            else {
                auto t = st.top();
                st.pop();
                f(x);
                st.emplace(t);
            }
        };
        f(val);
    }

    void pop() {
        if (!isEmpty())
            st.pop();
    }

    int peek() {
        return isEmpty() ? -1 : st.top();
    }

    bool isEmpty() {
        return st.empty();
    }
};

或者双栈:

class SortedStack {
    stack<int> st1, st2;

public:
    SortedStack() {}

    void push(int val) {
        if (st1.empty() || st1.top() >= val)
            st1.emplace(val);
        else {
            for (; !st1.empty() && st1.top() < val; st1.pop())
                st2.emplace(st1.top());
            st1.emplace(val);
            for (; !st2.empty(); st2.pop())
                st1.emplace(st2.top());
        }
    }

    void pop() {
        if (!isEmpty())
            st1.pop();
    }

    int peek() {
        return isEmpty() ? -1 : st1.top();
    }

    bool isEmpty() {
        return st1.empty();
    }
};

压入弹出序列

946. 验证栈序列 - 力扣（LeetCode）;剑指 Offer 31. 栈的压入、弹出序列 - 力扣（LeetCode）;

直接模拟即可..

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st;
        int n = pushed.size();
        for (int i{}, j{}; i < n; ++i) {
            st.emplace(pushed[i]);
            while (!st.empty() && st.top() == popped[j])
                ++j, st.pop();
        }
        return st.empty();
    }
};

用两个栈实现队列

232. 用栈实现队列 - 力扣（LeetCode）

class MyQueue {
    stack<int> in1, out1;

public:
    MyQueue() : in1(), out1() {}

    void push(int x) { in1.emplace(x); }

    int pop() {
        if (!out1.empty()) {
            int t{out1.top()};
            out1.pop();
            return t;
        }
        while (!in1.empty()) out1.emplace(in1.top()), in1.pop();
        int t1{out1.top()};
        out1.pop();
        return t1;
    }

    int peek() {
        int t{pop()};
        out1.emplace(t);
        return t;
    }

    bool empty() { return in1.empty() && out1.empty(); }
};

数组会快很多:

class MyQueue {
    vector<int> in1, out1;

public:
    MyQueue() : in1({}), out1({}) {}

    void push(int x) { in1.emplace_back(x); }

    int pop() {
        if (!out1.empty()) {
            int t{out1.back()};
            out1.pop_back();
            return t;
        }
        while (!in1.empty()) out1.emplace_back(in1.back()), in1.pop_back();
        int t1{out1.back()};
        out1.pop_back();
        return t1;
    }

    int peek() {
        int t{pop()};
        out1.emplace_back(t);
        return t;
    }

    bool empty() { return in1.empty() && out1.empty(); }
};

逆波兰表达式求值

栈的经典运用了

class Solution {
public:
    long atoi(string s) {
        long ans{};
        bool isNeg = s[0] == '-';
        for (int i = isNeg; i < s.size(); ++i) ans = 10 * ans + s[i] - '0';
        return isNeg ? -ans : ans;
    }
    int evalRPN(vector<string>& tokens) {
        int lhs{}, rhs{};
        stack<int> st;
        for (string s : tokens) {
            if (isdigit(s[0]) || s.size() > 1 && '-' == s[0])
                st.push(atoi(s));
            else if (s[0] == '+') {
                rhs = st.top(), st.pop();
                lhs = st.top(), st.pop();
                st.push(lhs + rhs);
            } else if (s[0] == '-') {
                rhs = st.top(), st.pop();
                lhs = st.top(), st.pop();
                st.push(lhs - rhs);
            } else if (s[0] == '*') {
                rhs = st.top(), st.pop();
                lhs = st.top(), st.pop();
                st.push(lhs * rhs);
            } else if (s[0] == '/') {
                rhs = st.top(), st.pop();
                lhs = st.top(), st.pop();
                st.push(lhs / rhs);
            }
        }
        return st.top();
    }
};

当然, 可以简化一下: (冗余代码太多了)

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        int n = tokens.size(), lhs, rhs;
        for (auto token : tokens) {
            if (isdigit(token[0]) || token.size() > 1 && token[0] == '-') {
                st.push(stoi(token));
            } else {
                rhs = st.top(), st.pop();
                lhs = st.top(), st.pop();
                switch (token[0]) {
                    case '+':
                        st.push(lhs + rhs);
                        break;
                    case '-':
                        st.push(lhs - rhs);
                        break;
                    case '*':
                        st.push(lhs * rhs);
                        break;
                    case '/':
                        st.push(lhs / rhs);
                        break;
                }
            }
        }
        return st.top();
    }
};

数组模拟栈

需要考虑数组开多大:

考虑到一个合法的逆波兰表达式数组, 其长度一定是一个奇数(至少是3, 每次加一个操作数加一个操作符)

并且, 操作数要比操作符的数量多一个, 那么就是 $\begin{cases} 操作数个数:&\frac{n+1}2\\ 操作符个数:&\frac{n-1}2 \end{cases}$ 这样一来, 数组长度选取为$\frac{n+1}2$即可满足条件.

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        int n = tokens.size(), idx = -1;
        int st[(n + 1) / 2];
        for (auto token : tokens) {
            if (isdigit(token[0]) || token.size() > 1 && token[0] == '-') {
                st[++idx] = stoi(token);
            } else {
                switch (token[0]) {
                    case '+':
                        --idx;
                        st[idx] += st[idx + 1];
                        break;
                    case '-':
                        --idx;
                        st[idx] -= st[idx + 1];
                        break;
                    case '*':
                        --idx;
                        st[idx] *= st[idx + 1];
                        break;
                    case '/':
                        --idx;
                        st[idx] /= st[idx + 1];
                        break;
                }
            }
        }
        return st[idx];
    }
};

递归解法

递归魔法, 相当于反着遍历

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        int idx = tokens.size() - 1;
        function<int()> f = [&]() {
            if (tokens[idx].size() == 1 && !isdigit(tokens[idx][0])) {
                char op = tokens[idx--][0];
                int rhs = f(), lhs = f(), ans{};
                switch (op) {
                    case '+':
                        ans = lhs + rhs;
                        break;
                    case '-':
                        ans = lhs - rhs;
                        break;
                    case '*':
                        ans = lhs * rhs;
                        break;
                    default:
                        ans = lhs / rhs;
                }
                return ans;
            }
            return stoi(tokens[idx--]);
        };
        return f();
    }
};

匹配替换后的单词

1003. 检查替换后的词是否有效;

队列进阶

用两个队列实现栈

225. 用队列实现栈 - 力扣（LeetCode）;

// STL 不讲武德版
class MyStack {
    deque<int> deq;

public:
    MyStack() {}

    void push(int x) { deq.emplace_back(x); }

    int pop() {
        int t = top();
        deq.pop_back();
        return t;
    }

    int top() { return deq.back(); }

    bool empty() { return deq.empty(); }
};

当然肯定得来个正经的:

class MyStack {
    queue<int> q1, q2;

public:
    MyStack() : q1(), q2() {}

    void push(int x) {
        if (q1.empty())
            q1.emplace(x);
        else {
            q2.emplace(x);
            for (; !empty(); q1.pop()) q2.emplace(q1.front());
            swap(q1, q2);
        }
    }

    int pop() {
        auto ans(top());
        q1.pop();
        return ans;
    }

    int top() { return q1.front(); }

    bool empty() { return q1.empty(); }
};

以及单队列实现:

class MyStack {
    queue<int> q;

public:
    MyStack() : q() {}

    void push(int x) {
        q.emplace(x);
        if (!q.empty())
            for (int n = q.size() - 1; n > 0; --n, q.pop())
                q.emplace(q.front());
    }

    int pop() {
        auto ans(top());
        q.pop();
        return ans;
    }

    int top() { return q.front(); }

    bool empty() { return q.empty(); }
};

循环队列

622. 设计循环队列;

需要知道下面的几个公式: $\begin{cases} size=(read-front+capcaity) \bmod capacity\\ empty: \ front == rear \\ full: \ front == (rear + 1) \bmod capacity \\ \end{cases}$

上面的变量名和下面代码中的 size 含义不同, 请注意.

class MyCircularQueue {
    int front, rear, size;
    vector<int> arr;

public:
    MyCircularQueue(int k) : front(0), rear(0), size(k + 1), arr(size) {}

    bool enQueue(int value) {
        if (isFull()) return false;
        arr[rear] = value;
        rear = (rear + 1) % size;
        return true;
    }

    bool deQueue() {
        if (isEmpty()) return false;
        front = (front + 1) % size;
        return true;
    }

    int Front() { return isEmpty() ? -1 : arr[front]; }

    int Rear() { return isEmpty() ? -1 : arr[(rear - 1 + size) % size]; }

    bool isEmpty() { return rear == front; }

    bool isFull() { return ((rear + 1) % size) == front; }
};

循环双端队列

641. 设计循环双端队列;

class MyCircularDeque {
    int front, rear, size; // front 指向头, rear 指向尾结点的下一个
    vector<int> arr;

public:
    MyCircularDeque(int k) : front(0), rear(0), size(k + 1), arr(size) {}

    bool insertFront(int value) {
        if (isFull()) return false;
        front = (front - 1 + size) % size;
        arr[front] = value;
        return true;
    }

    bool insertLast(int value) {
        if (isFull()) return false;
        arr[rear] = value;
        rear = (rear + 1) % size;
        return true;
    }

    bool deleteFront() {
        if (isEmpty()) return false;
        front = (front + 1) % size;
        return true;
    }

    bool deleteLast() {
        if (isEmpty()) return false;
        rear = (rear - 1 + size) % size;
        return true;
    }

    int getFront() { return isEmpty() ? -1 : arr[front]; }

    int getRear() { return isEmpty() ? -1 : arr[(rear - 1 + size) % size]; }

    bool isEmpty() { return rear == front; }

    bool isFull() { return ((rear + 1) % size) == front; }
};

单调栈

入门级

496. 下一个更大元素 I - 力扣（LeetCode）;(基本的单调栈题目)

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> mp;
        stack<int> st;
        for (auto num : nums2) {
            while (!st.empty() && num > st.top()) mp[st.top()] = num, st.pop();
            st.emplace(num);
        }
        for (auto& num : nums1) num = mp.count(num) ? mp[num] : -1;
        return nums1;
    }
};
// 反着遍历
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> mp;
        stack<int> st;
        for (int i = nums2.size() - 1; i >= 0; --i) {
            while (!st.empty() && nums2[i] > st.top()) st.pop();
            mp[nums2[i]] = st.empty() ? -1 : st.top();
            st.emplace(nums2[i]);
        }
        for (auto& num : nums1) num = mp[num];
        return nums1;
    }
};

503. 下一个更大元素 II - 力扣（LeetCode）;(循环数组, 关键是存索引和取模)
907. 子数组的最小值之和 - 力扣（LeetCode）;
2104. 子数组范围和 - 力扣（LeetCode）;(可暴力)
739. 每日温度;
1673. 找出最具竞争力的子序列;

进阶级

962. 最大宽度坡 - 力扣（LeetCode）;(单调栈求最长)
1124. 表现良好的最长时间段 - 力扣（LeetCode）;(上一个题的变式, 使用哈希更快, 而单调栈更普适)
654. 最大二叉树;(好题, 构造方法值得学习)
84. 柱状图中最大的矩形;

单调队列

模板

面试题59 - II. 队列的最大值;剑指 Offer 59 - II. 队列的最大值;

class MaxQueue {
    queue<int> q; // 存数据
    deque<int> d; // 存最大值
public:
    MaxQueue() : q(), d() {}

    int max_value() {
        if (d.empty()) return -1;
        return d.front();
    }

    void push_back(int value) {
        // 移除无用元素
        while (!d.empty() && d.back() < value) d.pop_back();
        d.push_back(value);
        q.emplace(value);
    }

    int pop_front() {
        if (q.empty()) return -1;
        auto ans{q.front()};
        // 如果待删除元素是最大值, d队头也要删除
        if (ans == d.front()) d.pop_front();
        q.pop();
        return ans;
    }
};

滑动窗口最大值

239. 滑动窗口最大值;剑指 Offer 59 - I. 滑动窗口的最大值;

方法 1: 优先队列

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        priority_queue<pair<int, int>> pq;
        vector<int> ans(n - k + 1);
        for (int i{}; i < k; ++i) pq.emplace(nums[i], i);
        ans[0] = pq.top().first;
        for (int i{k}; i < n; ++i) {
            pq.emplace(nums[i], i);
            while (!pq.empty() && pq.top().second <= i - k) pq.pop();
            ans[i - k + 1] = pq.top().first;
        }
        return ans;
    }
};

方法 2: 单调队列(经典方法)

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> ans(n - k + 1);
        deque<int> q;
        for (int i{}; i < n; ++i) {
            if (!q.empty() && q.front() == i - k) q.pop_front();
            while (!q.empty() && nums[i] > nums[q.back()]) q.pop_back();
            q.push_back(i);
            if (i >= k - 1) ans[i - k + 1] = nums[q.front()];
        }
        return ans;
    }
};

862. 和至少为 K 的最短子数组;

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

优先队列

1792. 最大平均通过率 - 力扣（LeetCode）;(需要了解到增量的递减性, 不错的优先队列题目)

class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        using pdii = pair<double, int>; // int存下标
        priority_queue<pdii> pq;
        int n = classes.size();
        for (int i{}; i < n; ++i) {
            int a{classes[i][0]}, b{classes[i][1]};
            double x = (a + 1.) / (b + 1) - a * 1. / b;
            pq.push({x, i});
        }
        while (extraStudents--) {
            auto [_, i] = pq.top();
            pq.pop();
            int &a{classes[i][0]}, &b{classes[i][1]};
            ++a, ++b;
            pq.push({(a + 1.) / (b + 1) - a * 1. / b, i});
        }
        double ans{};
        while (!pq.empty()) {
            auto [_, i] = pq.top();
            pq.pop();
            ans += classes[i][0] * 1. / classes[i][1];
        }
        return ans / n;
    }
};

剑指 Offer 41. 数据流中的中位数;295. 数据流的中位数;(通过有序集合也可以做, 但是需要考虑的点比较多)

class MedianFinder {
    priority_queue<int, vector<int>> queMin; // 大根堆
    //(堆顶元素是小于等于中位数的最大值)
    priority_queue<int, vector<int>, greater<int>> queMax; // 大于中位数的最小值
public:
    MedianFinder() {}
     
    void addNum(int num) {
        if (queMin.empty() || num <= queMin.top()) {
            queMin.emplace(num);
            // 调整(满足中位数性质)
            if (queMax.size() + 1 < queMin.size())
                queMax.emplace(queMin.top()), queMin.pop();
        } else {
            queMax.emplace(num);
            if (queMin.size() < queMax.size())
                queMin.emplace(queMax.top()), queMax.pop();
        }
    }
     
    double findMedian() {
        if (queMin.size() > queMax.size()) return queMin.top();
        return (queMin.top() + queMax.top()) / 2.0;
    }
};

手写堆实现: (模版才是好东西, 减少代码, 相当于生成代码的代码了, 所以才叫元编程)

template <typename T, class Compare = less<T>>
class Priority_Queue { // 默认小根堆
    vector<T> arr;
    size_t len;
    Compare comp;
     
public:
    Priority_Queue() : arr(), len() {}
     
    int top() { return arr[0]; }
    bool empty() { return len == 0; }
    int size() { return len; }
     
    void pop() {
        if (len == 0) return;
        arr[0] = arr[--len]; // 弹出队头元素
        arr.pop_back();
        int i{};
        for (;;) { // Heapify
            int tmp{i}, l{2 * i + 1}, r{2 * i + 2};
            if (l < len && comp(arr[l], arr[tmp])) tmp = l;
            if (r < len && comp(arr[r], arr[tmp])) tmp = r;
            if (tmp != i) {
                swap(arr[i], arr[tmp]);
                i = tmp;
            } else
                break;
        }
    }
    void push(int key) {
        arr.emplace_back(key);
        for (auto i{len++}; i > 0 && comp(arr[i], arr[(i - 1) / 2]);
             i = (i - 1) / 2)
            swap(arr[(i - 1) / 2], arr[i]);
    }
};
     
class MedianFinder {                     // 设中位数为 x
    Priority_Queue<int, greater<>> left; // 左半部分[min,x)
    Priority_Queue<int> right;           // 右边部分[x,max]
public:
    MedianFinder() {}
     
    void addNum(int num) {
        if (right.empty() || right.top() <= num) {
            right.push(num);
            if (right.size() > left.size() + 1)
                left.push(right.top()), right.pop();
        } else {
            left.push(num);
            if (left.size() > right.size()) right.push(left.top()), left.pop();
        }
    }
     
    double findMedian() {
        if (left.size() < right.size())
            return right.top();
        else
            return (left.top() + right.top()) / 2.;
    }
};

786. 第 K 个最小的素数分数 - 力扣（Leetcode）;

class Solution {
public:
    vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
        using ptype = pair<int, int>;
        auto cmp = [](const auto& lhs, const auto& rhs) {
            return lhs.first * rhs.second > lhs.second * rhs.first;
        };
        priority_queue<ptype, vector<ptype>, decltype(cmp)> pq(cmp);
        int n = arr.size();
        for (int i{}; i < n - 1; ++i)
            for (int j{i + 1}; j < n; ++j) pq.emplace(arr[i], arr[j]);
        for (int i{1}; i < k; ++i, pq.pop())
            ;
        return {pq.top().first, pq.top().second};
    }
};

23. 合并 K 个升序链表 - 力扣（Leetcode）;

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return {};
        auto cmp = [](const auto& lhs, const auto& rhs) {
            return lhs->val > rhs->val;
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
        int k = lists.size();
        auto dum = new ListNode, cur = dum;
        for (auto node : lists)
            if (node) pq.emplace(node);
     
        for (; !pq.empty(); pq.pop(), cur = cur->next) {
            auto tmp = pq.top();
            if (tmp) cur->next = tmp;
            if (tmp->next) pq.emplace(tmp->next);
        }
        return dum->next;
    }
};

1851. 包含每个查询的最小区间 - 力扣（LeetCode）;

上篇字符串与回文系列题目总结

下篇C++类内静态成员类外初始化情况分析与示例