力扣算法秘籍：STL容器适配器破解栈/队列问题

栈和队列是算法中的基础数据结构，STL提供的容器适配器能高效解决相关问题。以下是经典问题的解法秘籍：

一、栈适配器（stack）应用

问题：有效的括号（LeetCode 20）
验证括号字符串是否合法，如 "()[]{}" 有效，"(]" 无效。

bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') st.push(c);
        else {
            if (st.empty()) return false;
            char top = st.top();
            if ((c == ')' && top != '(') || 
                (c == ']' && top != '[') || 
                (c == '}' && top != '{')) return false;
            st.pop();
        }
    }
    return st.empty();
}

核心思想：
遇到左括号入栈，右括号时检查栈顶是否匹配。时间复杂度：$O(n)$，空间复杂度：$O(n)$。

---

二、队列适配器（queue）应用

问题：用栈实现队列（LeetCode 232）
仅用栈操作实现队列的 push、pop、peek、empty。

class MyQueue {
private:
    stack<int> in, out;
    
    void transfer() {
        while (!in.empty()) {
            out.push(in.top());
            in.pop();
        }
    }
public:
    void push(int x) { in.push(x); }
    
    int pop() {
        if (out.empty()) transfer();
        int val = out.top();
        out.pop();
        return val;
    }
    
    int peek() {
        if (out.empty()) transfer();
        return out.top();
    }
    
    bool empty() { return in.empty() && out.empty(); }
};

设计要点：

• in 栈处理入队，out 栈处理出队
• 当 out 为空时，将 in 中元素全部转移
• 均摊时间复杂度：$O(1)$

---

三、优先级队列（priority_queue）应用

问题：数组中的第K大元素（LeetCode 215）
在未排序数组中找到第K大的元素，如 [3,2,1,5,6,4] 的K=2时返回5。

int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> pq; // 最小堆
    
    for (int num : nums) {
        pq.push(num);
        if (pq.size() > k) pq.pop();
    }
    return pq.top();
}

优化策略：

• 维护大小为K的最小堆
• 堆顶即为第K大元素
• 时间复杂度：$O(n \log k)$

---

四、综合应用：滑动窗口最大值（LeetCode 239）

问题：给定数组和窗口大小k，返回每个窗口的最大值序列。
如 nums = [1,3,-1,-3,5,3,6,7], k = 3 时输出 [3,3,5,5,6,7]。

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq; // 双端队列存储索引
    vector<int> res;
    
    for (int i = 0; i < nums.size(); ++i) {
        // 移除超出窗口的元素
        if (!dq.empty() && dq.front() == i - k) dq.pop_front();
        
        // 维护单调递减队列
        while (!dq.empty() && nums[dq.back()] < nums[i]) 
            dq.pop_back();
        
        dq.push_back(i);
        if (i >= k - 1) res.push_back(nums[dq.front()]);
    }
    return res;
}

关键技巧：

1. 使用双端队列维护索引而非值
2. 队列保持单调递减（队头始终为最大值）
3. 时间复杂度：$O(n)$，空间复杂度：$O(k)$

总结：STL适配器的核心优势

1. stack：后进先出（LIFO），适合对称性问题
2. queue：先进先出（FIFO），适合顺序处理
3. priority_queue：自动排序，适合TopK问题
   掌握这些工具能高效解决90%的栈/队列相关问题！