栈

单调栈（基础/矩形面积/贡献法/最小字典序）

单调栈：概念与基础

单调栈是一种特殊的栈，栈内元素按某种单调顺序排列（单调递增或单调递减）。它的特点是：

• 保持单调性：栈中元素始终保持递增或递减。
• 高效处理范围问题：常用于快速找到每个元素左右两侧第一个比它大或小的元素。
• 时间复杂度：一般为 ( O(n) )，每个元素最多入栈和出栈一次。

---

1. 单调栈基础

1.1 核心操作

• 单调递增栈：栈内元素从栈底到栈顶递增，弹出时处理的是右边比当前元素小的逻辑。
• 单调递减栈：栈内元素从栈底到栈顶递减，弹出时处理的是右边比当前元素大的逻辑。

1.2 模板代码

以单调递增栈为例：

func nextGreaterElements(nums []int) []int {
    n := len(nums)
    res := make([]int, n)
    stack := []int{} // 存索引而非值

    for i := 0; i < n; i++ {
        // 保证栈内单调递增
        for len(stack) > 0 && nums[stack[len(stack)-1]] < nums[i] {
            res[stack[len(stack)-1]] = nums[i]
            stack = stack[:len(stack)-1] // 弹出栈顶
        }
        stack = append(stack, i) // 当前索引入栈
    }

    // 栈中剩余元素表示其右边没有更大的值
    for len(stack) > 0 {
        res[stack[len(stack)-1]] = -1
        stack = stack[:len(stack)-1]
    }
    return res
}

---

2. 单调栈与矩形面积

2.1 问题：柱状图中的最大矩形

给定一个柱状图数组 heights，每个柱的宽度为 1，求柱状图中能勾勒出的矩形的最大面积。

思路

1. 对每根柱子，确定其左右两边第一个小于它的柱子。
2. 柱子的宽度范围为左右两个柱子间的距离。
3. 使用单调递增栈快速找到每根柱子的左右边界。

实现

func largestRectangleArea(heights []int) int {
    heights = append(heights, 0) // 哨兵，保证栈中能清空
    stack := []int{}
    maxArea := 0

    for i := 0; i < len(heights); i++ {
        // 栈顶元素大于当前柱子时，弹出并计算面积
        for len(stack) > 0 && heights[stack[len(stack)-1]] > heights[i] {
            h := heights[stack[len(stack)-1]]
            stack = stack[:len(stack)-1] // 弹出栈顶
            w := i
            if len(stack) > 0 {
                w = i - stack[len(stack)-1] - 1 // 宽度
            }
            maxArea = max(maxArea, h*w)
        }
        stack = append(stack, i) // 当前索引入栈
    }
    return maxArea
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

---

3. 单调栈与贡献法

贡献法是一种利用单调栈思想快速计算数组元素“贡献值”的技巧。

3.1 问题：所有子数组中的最小值之和

给定一个数组 arr，计算所有子数组中的最小值的和。

思路

1. 核心：找到每个元素作为子数组最小值的贡献范围。
   • 左边界：第一个小于等于当前元素的元素索引。
   • 右边界：第一个小于当前元素的元素索引。
2. 计算每个元素的贡献值：
   • 贡献次数：左边界到当前元素长度 × 当前元素到右边界长度。
   • 贡献值：贡献次数 × 元素值。

实现

func sumOfSubarrayMins(arr []int) int {
    const mod = 1e9 + 7
    n := len(arr)
    left, right := make([]int, n), make([]int, n)
    stack := []int{}

    // 找左边第一个小于等于当前元素的索引
    for i := 0; i < n; i++ {
        for len(stack) > 0 && arr[stack[len(stack)-1]] > arr[i] {
            stack = stack[:len(stack)-1]
        }
        if len(stack) == 0 {
            left[i] = -1
        } else {
            left[i] = stack[len(stack)-1]
        }
        stack = append(stack, i)
    }

    stack = []int{}
    // 找右边第一个小于当前元素的索引
    for i := n - 1; i >= 0; i-- {
        for len(stack) > 0 && arr[stack[len(stack)-1]] >= arr[i] {
            stack = stack[:len(stack)-1]
        }
        if len(stack) == 0 {
            right[i] = n
        } else {
            right[i] = stack[len(stack)-1]
        }
        stack = append(stack, i)
    }

    // 计算贡献值
    result := 0
    for i := 0; i < n; i++ {
        count := (i - left[i]) * (right[i] - i) // 贡献次数
        result = (result + count*arr[i]) % mod
    }
    return result
}

---

4. 单调栈与最小字典序

问题：移掉 K 位数字

给定一个数字字符串 num 和一个整数 k，从中移除 k 位数字，使剩下的数字最小。

思路

1. 单调栈维护一个递增序列，遇到比栈顶元素小的数字时弹出栈顶。
2. 保证栈中数字的个数为 ( len(num) - k )。

实现

func removeKdigits(num string, k int) string {
    stack := []byte{}

    for i := 0; i < len(num); i++ {
        // 弹出栈顶以保证字典序最小
        for len(stack) > 0 && stack[len(stack)-1] > num[i] && k > 0 {
            stack = stack[:len(stack)-1]
            k--
        }
        stack = append(stack, num[i])
    }

    // 如果还有未移除的字符
    stack = stack[:len(stack)-k]

    // 去掉前导零
    result := string(stack)
    for len(result) > 1 && result[0] == '0' {
        result = result[1:]
    }

    if result == "" {
        return "0"
    }
    return result
}

---

5. 总结

• 单调栈核心：通过栈的单调性快速找到范围界限。
• 应用场景：
  • 找最近更大/更小元素。
  • 计算矩形面积、贡献值等区间问题。
  • 构造最优解（如最小字典序）。
• 优化技巧：结合左右边界的思想，使问题分解为简单的局部操作。