题目 1：用栈实现队列

题目描述

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）。

解题思路

双栈分工：

• inStack：负责入队操作，push 直接压入此栈
• outStack：负责出队操作 当outStack为空时，将inStack中所有元素依次弹出并压入outStack，此时outStack的栈顶就是队首元素。

代码实现

cpp

运行

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

复杂度分析

• 时间复杂度：每个元素最多入栈和出栈各两次，均摊时间复杂度 O (1)
• 空间复杂度：O (n)

面试考点

考察栈与队列的特性转换。面试官常反向问：用队列实现栈怎么做？

题目 2：有效的括号

题目描述

给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合，左括号必须以正确的顺序闭合。

解题思路

栈匹配法： 遍历字符串，遇到左括号就将对应的右括号压入栈；遇到右括号时，检查栈是否为空或栈顶是否与当前字符匹配，不匹配则直接返回 false，匹配则弹出栈顶。最后栈为空则说明全部匹配。

代码实现

cpp

运行

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

复杂度分析

• 时间复杂度：O (n)，一次遍历
• 空间复杂度：O (n)，最坏情况全是左括号

面试考点

栈的经典应用。延伸问：如果只有一种括号怎么优化空间？怎么计算最长有效括号长度？

题目 3：最小栈

题目描述

设计一个支持push，pop，top操作，并能在常数时间内检索到最小元素的栈。

解题思路

辅助栈法： 用两个栈，主栈正常存储元素，辅助栈同步存储当前最小值。每次 push 时，辅助栈压入「当前值与辅助栈栈顶的较小值」；pop 时两个栈同步弹出。这样辅助栈的栈顶永远是当前栈内的最小值。

代码实现

cpp

运行

class MinStack { private: stack<int> mainStack; stack<int> minStack; public: MinStack() { minStack.push(INT_MAX); // 初始压入最大值，方便第一次比较 } void push(int val) { mainStack.push(val); minStack.push(min(minStack.top(), val)); } void pop() { mainStack.pop(); minStack.pop(); } int top() { return mainStack.top(); } int getMin() { return minStack.top(); } };

复杂度分析

• 所有操作时间复杂度：O (1)
• 空间复杂度：O (n)，辅助栈占用额外空间

面试考点

考察空间换时间的设计思想。面试官常追问：不使用额外栈怎么实现？（可用差值法，用一个变量存最小值）

题目 4：滑动窗口最大值

题目描述

给你一个整数数组nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字，滑动窗口每次只向右移动一位。返回每个滑动窗口中的最大值。

解题思路

单调队列： 维护一个单调递减的双端队列，队列中存储元素的索引：

1. 新元素入队前，弹出队尾所有比它小的元素，保证队列递减
2. 检查队首元素是否超出窗口范围，超出则弹出队首
3. 当窗口形成（索引 ≥ k-1）后，队首就是当前窗口的最大值

代码实现

cpp

运行

vector<int> maxSlidingWindow(vector<int>& nums, int k) { deque<int> dq; // 存储索引，保持对应值递减 vector<int> res; for (int i = 0; i < nums.size(); i++) { // 弹出队尾比当前值小的元素 while (!dq.empty() && nums[i] >= nums[dq.back()]) { dq.pop_back(); } dq.push_back(i); // 弹出超出窗口的队首 while (dq.front() <= i - k) { dq.pop_front(); } // 窗口形成后记录结果 if (i >= k - 1) { res.push_back(nums[dq.front()]); } } return res; }

复杂度分析

• 时间复杂度：O (n)，每个元素最多入队和出队一次
• 空间复杂度：O (k)，队列长度不超过窗口大小

面试考点

单调队列的经典应用，是面试拔高题。重点考察对数据结构特性的灵活运用。