题目 1用栈实现队列题目描述请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作push、pop、peek、empty。解题思路双栈分工inStack负责入队操作push 直接压入此栈outStack负责出队操作 当outStack为空时将inStack中所有元素依次弹出并压入outStack此时outStack的栈顶就是队首元素。代码实现cpp运行class MyQueue { private: stackint 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) { stackchar 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最小栈题目描述设计一个支持pushpoptop操作并能在常数时间内检索到最小元素的栈。解题思路辅助栈法 用两个栈主栈正常存储元素辅助栈同步存储当前最小值。每次 push 时辅助栈压入「当前值与辅助栈栈顶的较小值」pop 时两个栈同步弹出。这样辅助栈的栈顶永远是当前栈内的最小值。代码实现cpp运行class MinStack { private: stackint mainStack; stackint 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个数字滑动窗口每次只向右移动一位。返回每个滑动窗口中的最大值。解题思路单调队列 维护一个单调递减的双端队列队列中存储元素的索引新元素入队前弹出队尾所有比它小的元素保证队列递减检查队首元素是否超出窗口范围超出则弹出队首当窗口形成索引 ≥ k-1后队首就是当前窗口的最大值代码实现cpp运行vectorint maxSlidingWindow(vectorint nums, int k) { dequeint dq; // 存储索引保持对应值递减 vectorint 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)队列长度不超过窗口大小面试考点单调队列的经典应用是面试拔高题。重点考察对数据结构特性的灵活运用。谢谢