栈与队列

栈和队列是两种基础的数据结构，栈先进后出（LIFO），队列先进先出（FIFO）。在算法题中，栈常用于匹配问题、单调问题和递归模拟，队列则常用于BFS和调度。本模块涵盖有效的括号、用栈实现队列、每日温度、柱状图中最大的矩形等经典题型。

---

Q1: 有效的括号 「🟢 初级」

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

考察点：栈的应用、括号匹配、HashMap映射。

解题思路：

• 方法：栈，遇到左括号入栈，遇到右括号检查栈顶是否匹配（时间O(n)，空间O(n)）- 最优解

代码实现：

public boolean isValid(String s) {
    Map<Character, Character> map = new HashMap<>();
    map.put(')', '(');
    map.put(']', '[');
    map.put('}', '{');
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (map.containsKey(c)) { // 右括号
            if (stack.isEmpty() || stack.peek() != map.get(c)) {
                return false;
            }
            stack.pop();
        } else { // 左括号
            stack.push(c);
        }
    }
    return stack.isEmpty();
}

复杂度分析：时间复杂度 O(n)，遍历一次字符串；空间复杂度 O(n)，最坏情况全是左括号。

变体扩展：

• 变体1：最长有效括号
• 变体2：括号生成
• 变体3：删除无效的括号
• 变体4：有效括号的嵌套深度

---

Q2: 用栈实现队列 「🟢 初级」

题目描述：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）。你只能使用标准的栈操作 —— 也就是只有 push to top、peek/pop from top、size、和 is empty 操作是合法的。

考察点：栈和队列的特性、双栈设计。

解题思路：

• 方法：两个栈，一个输入栈负责push，一个输出栈负责pop/peek。输出栈空时把输入栈全部弹入输出栈（摊还时间O(1)，空间O(n)）- 最优解

代码实现：

class MyQueue {
    Deque<Integer> inStack;
    Deque<Integer> outStack;
    
    public MyQueue() {
        inStack = new ArrayDeque<>();
        outStack = new ArrayDeque<>();
    }
    
    public void push(int x) {
        inStack.push(x);
    }
    
    public int pop() {
        if (outStack.isEmpty()) {
            inToOut();
        }
        return outStack.pop();
    }
    
    public int peek() {
        if (outStack.isEmpty()) {
            inToOut();
        }
        return outStack.peek();
    }
    
    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }
    
    private void inToOut() {
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
    }
}

复杂度分析：push时间O(1)，pop和peek摊还时间O(1)（每个元素最多被移动一次）；空间复杂度 O(n)。

变体扩展：

• 变体1：用队列实现栈
• 变体2：设计循环队列
• 变体3：设计双端队列

---

Q3: 用队列实现栈 「🟢 初级」

题目描述：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。

考察点：队列和栈的特性、双队列/单队列设计。

解题思路：

• 方法1：两个队列，push时用辅助队列倒一下（时间O(n) push，O(1) pop）
• 方法2：一个队列，push时把前面的元素移到后面（时间O(n) push，O(1) pop）- 最优解

代码实现：

class MyStack {
    Queue<Integer> queue;
    
    public MyStack() {
        queue = new LinkedList<>();
    }
    
    public void push(int x) {
        int size = queue.size();
        queue.offer(x);
        for (int i = 0; i < size; i++) {
            queue.offer(queue.poll());
        }
    }
    
    public int pop() {
        return queue.poll();
    }
    
    public int top() {
        return queue.peek();
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }
}

复杂度分析：push时间O(n)，pop和top时间O(1)；空间复杂度 O(n)。

变体扩展：

• 变体1：用栈实现队列
• 变体2：设计循环双端队列
• 变体3：最小栈

---

Q4: 每日温度 「🟡 中级」

题目描述：给定一个整数数组 temperatures，表示每天的温度，返回一个数组 answer，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

考察点：单调栈、下一个更大元素。

解题思路：

• 方法1：暴力解法（时间O(n²)，空间O(1)）
• 方法2：单调栈，维护一个温度递减的下标栈（时间O(n)，空间O(n)）- 最优解

代码实现：

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] res = new int[n];
    Deque<Integer> stack = new ArrayDeque<>(); // 存下标，温度递减
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int prev = stack.pop();
            res[prev] = i - prev;
        }
        stack.push(i);
    }
    return res;
}

复杂度分析：时间复杂度 O(n)，每个元素最多入栈出栈各一次；空间复杂度 O(n)。

变体扩展：

• 变体1：下一个更大元素I
• 变体2：下一个更大元素II（循环数组）
• 变体3：柱状图中最大的矩形
• 变体4：接雨水

---

Q5: 最小栈 「🟢 初级」

题目描述：设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。实现 MinStack 类：MinStack() 初始化堆栈对象，void push(int val) 将元素推入栈中，void pop() 删除栈顶的元素，int top() 获取栈顶元素，int getMin() 检索栈中的最小元素。

考察点：辅助栈、单调栈、数据结构设计。

解题思路：

• 方法1：两个栈，一个存数据，一个存当前最小值（时间O(1)各操作，空间O(n)）- 最优解
• 方法2：一个栈存差值，用一个变量记录最小值
• 方法3：链表节点存min值

代码实现：

class MinStack {
    Deque<Integer> dataStack;
    Deque<Integer> minStack;
    
    public MinStack() {
        dataStack = new ArrayDeque<>();
        minStack = new ArrayDeque<>();
    }
    
    public void push(int val) {
        dataStack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        } else {
            minStack.push(minStack.peek()); // 同步压入当前最小值
        }
    }
    
    public void pop() {
        dataStack.pop();
        minStack.pop();
    }
    
    public int top() {
        return dataStack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

复杂度分析：push、pop、top、getMin 时间复杂度均为 O(1)；空间复杂度 O(n)，两个栈各存n个元素。

变体扩展：

• 变体1：最大栈
• 变体2：最小队列
• 变体3：全O(1)的数据结构
• 变体4：滑动窗口最大值

---

Q6: 柱状图中最大的矩形 「🔴 高级」

题目描述：给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。求在该柱状图中，能够勾勒出来的矩形的最大面积。

考察点：单调栈、下一个更小元素、面积计算。

解题思路：

• 方法1：暴力枚举（时间O(n²)，空间O(1)）
• 方法2：单调栈，找每个柱子左右第一个比它小的位置，宽度为两者之差（时间O(n)，空间O(n)）- 最优解

代码实现：

public int largestRectangleArea(int[] heights) {
    int n = heights.length;
    int[] left = new int[n]; // 左边第一个比heights[i]小的下标
    int[] right = new int[n]; // 右边第一个比heights[i]小的下标
    Deque<Integer> stack = new ArrayDeque<>();
    
    // 找左边界
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
            stack.pop();
        }
        left[i] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(i);
    }
    stack.clear();
    
    // 找右边界
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
            stack.pop();
        }
        right[i] = stack.isEmpty() ? n : stack.peek();
        stack.push(i);
    }
    
    // 计算面积
    int maxArea = 0;
    for (int i = 0; i < n; i++) {
        maxArea = Math.max(maxArea, heights[i] * (right[i] - left[i] - 1));
    }
    return maxArea;
}

复杂度分析：时间复杂度 O(n)，每个元素入栈出栈各两次；空间复杂度 O(n)，两个边界数组和栈。

变体扩展：

• 变体1：最大矩形（矩阵中的最大矩形）
• 变体2：接雨水
• 变体3：每日温度
• 变体4：去除重复字母