Go语言单调栈入门详解

本文深入浅出地讲解了Go语言中如何用切片高效模拟单调栈，强调其核心并非封装栈结构，而是精准控制入栈时的弹出逻辑以维持单调性——递增栈用于寻找更小值，递减栈用于寻找更大值；通过“每个元素最多进出一次”轻松保证O(n)时间复杂度，并直击初学者最常踩的三大坑：比较符写错、单调方向搞反、哨兵边界忽略，帮你避开80%的调试陷阱，快速掌握这一高频算法利器。

Go 语言实现单调栈，核心不是“写个栈”，而是用数组模拟栈+控制入栈时的弹出逻辑——只要记住“每个元素最多进、出一次”，就能稳住 O(n) 时间复杂度。

怎么用切片模拟单调栈（不写 Stack 结构体）

Go 标准库没有内置栈类型，但用 []int 切片 + append/[:len-1] 就足够高效。关键不是封装，而是维护单调性时的判断方向：

• 单调递增栈（栈底小 → 栈顶大）：入栈前弹出所有 >= 当前值 的元素 → 用于找「左侧第一个更小值」或「右侧第一个更小值」
• 单调递减栈（栈底大 → 栈顶小）：入栈前弹出所有 的元素 → 用于找「下一个更大元素」nextGreaterElement
• 别存值，存下标！比如 st = append(st, i)，需要值时查 a[i] —— 这样才能算位置差（如温度题的天数）、边界宽度（如接雨水、最大矩形）

为什么倒序遍历常比正序更直觉（以 nextGreaterElement 为例）

倒序时，栈里存的是「右边已处理过的候选更大值」，当前元素一来，就把所有比它矮的全踢掉，栈顶自然就是它右边第一个更高的人。正序也能做，但逻辑是「等更大值出现时，回头填之前那些人的答案」，容易绕晕：

for i := n-1; i >= 0; i-- {
    for len(st) > 1 && a[st[len(st)-1]] <p>注意：<code>st := []int{n}</code> 是常见哨兵写法，避免每次判空；若用 <code>st := []int{}</code>，就得写 <code>if len(st) > 0</code>，多一层分支。</p><h3>最容易踩的三个坑</h3><p>写错比较符、搞反单调方向、忽略边界哨兵——这三个错误加起来占初学者调试时间的 80%：</p>

• a[st[len(st)-1]] 和 混用：严格「下一个更大」用 ；「下一个大于等于」才用 —— LeetCode 496 和 739 要求不同
• 误把「递增栈」当成「找更大元素」：错！递增栈（栈底小）天然适合找「更小值的边界」；找「更大值」得用递减栈（栈底大）
• 没处理无解情况：比如 right[i] == n 表示右边没有更大元素，该填 0 或 -1，别直接用 a[right[i]] 访问越界

接雨水 / 最大矩形这类题，为什么必须用单调栈而不是双指针

因为它们本质不是「全局最值」，而是「每个柱子能向左右扩展到哪」——这个左右边界，恰好就是「左侧第一个更小」和「右侧第一个更小」，单调栈能在一遍扫描中同时搞定两个边界，而双指针或暴力要 O(n²)。

例如直方图最大矩形：对每个 height[i]，算出 left[i] 和 right[i] 后，面积就是 height[i] * (right[i] - left[i] - 1)。这里 left 和 right 数组，就是单调栈最朴实的输出产物。

真正难的不是写栈，是想清楚：你要的「边界」到底满足什么条件？然后选对单调性、遍历方向、比较符号——剩下的就是机械地推下标。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《Go语言单调栈入门详解》文章吧，也可关注golang学习网公众号了解相关技术文章。