算法与数据结构笔记：栈与单调栈演进

希望尽快改成用Golang做算法吧。。。尽快熟练Golang的语法，AI时代不手搓学语法有点不自然。

---

容器选择

1. 为什么不用 java.util.Stack？

• 继承自 Vector，所有方法带 synchronized 锁，单线程下性能损耗大。
• 暴露了按索引随机访问的接口，破坏了 LIFO 的封装约束。

2. 容器选型对比

方案	底层结构	内存与装箱	适用场景
LinkedList	双向链表	频繁 new Node，指针跳跃，开销最大	❌ 严禁用于栈/队列操作
ArrayDeque	循环动态数组	连续内存，但基础类型存在装箱/拆箱开销	业务工程首选（类型安全、动态扩容）
原生数组模拟	int[] + top	零额外对象、零装箱拆箱、CPU 缓存命中极高	算法刷题首选（0ms）

---

数组模拟栈核心模板

当题目输入规模 $N$ 已知且栈深度不超过 $N$ 时使用：

int[] stack = new int[n];
int top = -1; // -1 表示空栈

stack[++top] = val;         // push：压栈
int val = stack[top--];     // pop：弹栈
int topVal = stack[top];    // peek：查看栈顶
boolean isEmpty = top == -1;// isEmpty：判空

---

三种写法横向对比：LeetCode 739. 每日温度

问题：给定每天温度，求之后第几天会出现更高的温度（下一个更大元素距离）。 核心模型：单调递减栈（栈底到栈顶单调递减，存下标）。遇到更高温度时持续 pop 批量结算。

写法 1：常见官方低效写法（LinkedList + 包装类）

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ans = new int[n];
        Deque<Integer> stack = new LinkedList<Integer>(); // 频繁 new Node，效率低
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int prev = stack.pop();
                ans[prev] = i - prev;
            }
            stack.push(i); // 发生 int -> Integer 自动装箱
        }
        return ans;
    }
}

写法 2：标准工程写法（ArrayDeque）

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ans = 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();
                ans[prev] = i - prev;
            }
            stack.push(i);
        }
        return ans;
    }
}

写法 3：刷题极致性能写法（原生 int[] 模拟栈，0ms）

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ans = new int[n];
        int[] stack = new int[n]; // 原生数组，消除对象分配与装箱开销
        int top = -1;

        for (int i = 0; i < n; i++) {
            while (top >= 0 && temperatures[i] > temperatures[stack[top]]) {
                int prev = stack[top--];
                ans[prev] = i - prev;
            }
            stack[++top] = i;
        }
        return ans;
    }
}

---

经典题型：数组模拟单调栈实战

1. LeetCode 20. 有效的括号（普通栈）

思路：遇到左括号，将其期望闭合的“右括号”直接压栈；遇到右括号，检查栈顶是否相等。

class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 != 0) return false;

        char[] stack = new char[n];
        int top = -1;

        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == '(') stack[++top] = ')';
            else if (c == '[') stack[++top] = ']';
            else if (c == '{') stack[++top] = '}';
            else if (top == -1 || stack[top--] != c) return false;
        }
        return top == -1;
    }
}

2. LeetCode 496. 下一个更大元素 I（单调栈 + 索引哈希）

思路：用单调递减栈预处理 nums2 中每个元素右侧第一个更大的值，并存入哈希映射。

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] stack = new int[nums2.length];
        int top = -1;

        for (int num : nums2) {
            while (top >= 0 && num > stack[top]) {
                map.put(stack[top--], num); // 栈顶元素找到了右侧更大值
            }
            stack[++top] = num;
        }

        int[] ans = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            ans[i] = map.getOrDefault(nums1[i], -1);
        }
        return ans;
    }
}

3. LeetCode 42. 接雨水（单调栈横向结算）

思路：维护单调递减栈。当出现高度抬升时，栈顶为凹槽底部（bottom），新的栈顶为左边界，当前遍历位置为右边界，横向计算积水面积。

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int[] stack = new int[n];
        int top = -1;
        int totalWater = 0;

        for (int i = 0; i < n; i++) {
            while (top >= 0 && height[i] > height[stack[top]]) {
                int bottom = stack[top--]; // 凹槽底部
                if (top == -1) break;      // 没有左边界，无法蓄水

                int left = stack[top];
                int h = Math.min(height[left], height[i]) - height[bottom];
                int w = i - left - 1;
                totalWater += h * w;
            }
            stack[++top] = i;
        }
        return totalWater;
    }
}

---

关键解题原则总结

• 复杂度证明：每个元素最多入栈 1 次、出栈 1 次，单调栈整体时间复杂度严格为 $O(N)$，非暴力嵌套。

• 方向口诀：

• 找下一个更大元素 $\rightarrow$ 单调递减栈（遇大则弹）。

• 找下一个更小元素 $\rightarrow$ 单调递增栈（遇小则弹）。

• 存储习惯：单调栈内优先存储下标（既能索引数值，又能计算距离和宽度）。