leetcode面试笔试-双指针题型总结

1. 常用表格总结

2. 常用解题思路

• 栈（Stack）

  • 括号匹配类：遇到左括号入栈，遇到右括号检查栈顶

  • 单调栈：维护单调递增/递减栈，用于“下一个更大/更小元素”

  • 模拟函数调用：递归展开或表达式求值

• // 栈常见写法
  Stack<Integer> stack = new Stack<>();// 入栈
  stack.push(x);// 出栈
  int val = stack.pop();// 查看栈顶
  int top = stack.peek();// 判空
  if(stack.isEmpty()) { ... }
  

• 队列（Queue）

  • BFS：树/图最短路径，逐层扩展

  • 层序遍历：树按层输出

  • 循环队列：利用数组实现环形结构

• // 普通队列
  Queue<Integer> queue = new LinkedList<>();// 入队
  queue.offer(x);// 出队
  int val = queue.poll();// 查看队头
  int head = queue.peek();// 判空
  if(queue.isEmpty()) { ... }
  

• 双端队列（Deque）

  • 单调队列：保证队首是最大/最小值，常用于滑动窗口问题

  • 双向扩展搜索（BFS 优化）

• 优先队列（Heap）

  • 维护动态区间的最大/最小值

  • 经典应用：前 K 个最大值，合并 K 个有序列表

3. 常见注意点

• 栈模拟递归时要注意 栈溢出 问题

• 队列的 BFS 中要注意 访问过的节点要标记（避免死循环）

• 单调栈/队列需要 合理出栈/出队 保证单调性

• 循环队列数组实现时下标要用 取模运算

4. 高频模板

栈：括号匹配（LC 20）

public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for (char c : s.toCharArray()) {if (c == '(') stack.push(')');else if (c == '[') stack.push(']');else if (c == '{') stack.push('}');else if (stack.isEmpty() || stack.pop() != c) return false;}return stack.isEmpty();
}

单调栈：下一个更大元素（LC 496/739）

Stack<Integer> st = new Stack<>();
for (int i = n - 1; i >= 0; i--) {while (!st.isEmpty() && st.peek() <= nums[i]) st.pop();ans[i] = st.isEmpty() ? -1 : st.peek();st.push(nums[i]);
}

队列：BFS 层序遍历（LC 102）

Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {int size = q.size();List<Integer> level = new ArrayList<>();for (int i = 0; i < size; i++) {TreeNode node = q.poll();level.add(node.val);if (node.left != null) q.offer(node.left);if (node.right != null) q.offer(node.right);}ans.add(level);
}

单调队列：滑动窗口最大值（LC 239）

Deque<Integer> dq = new ArrayDeque<>();
for (int i = 0; i < n; i++) {if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();dq.offerLast(i);if (i >= k - 1) ans[i - k + 1] = nums[dq.peekFirst()];
}

5 leetcode题目

232用栈实现队列

class MyQueue {private Stack<Integer> inStack;private Stack<Integer> outStack;public MyQueue() {inStack = new Stack<>();outStack = new Stack<>();}  public void push(int x) {inStack.push(x);}public int pop() {shiftStack();return outStack.pop();}public int peek() {shiftStack();return outStack.peek();}public boolean empty() {return inStack.isEmpty() && outStack.isEmpty();}private void  shiftStack(){if(outStack.isEmpty()){while(!inStack.isEmpty()){outStack.push(inStack.pop());}}}
}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj = new MyQueue();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.peek();* boolean param_4 = obj.empty();*/

225用队列实现栈

class MyStack {private Queue<Integer> queue1;private Queue<Integer> queue2;public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}public void push(int x) {queue2.offer(x); //暂时while(!queue1.isEmpty()){queue2.offer(queue1.poll());}Queue<Integer> temp = queue1;queue1 = queue2;queue2 = temp;}public int pop() {return queue1.poll();}public int top() {return queue1.peek();}public boolean empty() {return queue1.isEmpty();}
}/*** Your MyStack object will be instantiated and called as such:* MyStack obj = new MyStack();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.top();* boolean param_4 = obj.empty();*/