数据结构（6）: 单调栈

特性

单调栈是一种特殊的栈数据结构，它满足元素的单调性（单调递增或单调递减）。与普通栈相比，单调栈在出栈时有一定的规则，使得出栈后栈中的元素仍然保持单调性。

单调栈主要有两个操作：入栈和出栈。入栈时，先判断栈顶元素是否符合单调性，如果不符合，则将其弹出，一直重复此过程直到符合单调性后再入栈；出栈时，弹出栈顶元素即可。

算法应用

单调栈在算法中有许多应用，例如在求解 Next Greater Element（下一个更大元素）等问题中。

以求解 Next Greater Element 问题为例，给定一个数组 nums，要求找出每个元素的下一个更大元素（即在数组中右边第一个比它大的数），若不存在则为-1。我们可以使用单调栈来解决这个问题。

具体的实现步骤如下：

遍历数组 nums，依次将元素入栈
当栈顶元素小于当前元素时，弹出栈顶元素，将其下一个更大元素设为当前元素，并继续弹出栈顶元素，直到栈为空或栈顶元素大于等于当前元素
当遍历完数组后，栈中剩余的元素的下一个更大元素均为-1

实例代码：

func nextGreaterElement(nums []int) []int {
    stack := []int{}
    res := make([]int, len(nums))
    for i := range res {
        res[i] = -1
    }
    for i := 0; i < len(nums); 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)
    }
    return res
}

实战

1. 每日温度

LeetCode 739. 每日温度

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

该问题就是典型的 Next Greater Element（下一个更大元素） 问题，题目等价于找出右边第一个比当前元素大的距离。

示例代码:

func dailyTemperatures(temperatures []int) []int {
    n := len(temperatures)
    ans := make([]int, n)
    stk := []int{}
    for i := 0; i < n; i++ {
        for len(stk) > 0 && temperatures[i] > temperatures[stk[len(stk)-1]] {
            top := stk[len(stk)-1]
            stk = stk[:len(stk)-1]
            ans[top] = i - top
        }
        stk = append(stk, i)
    }
    return ans
}

2. 循环数组下一个更大元素

LeetCode 503. 下一个更大元素 II

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的下一个更大元素。
数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

该问题和题目 739. 每日温度 类似，不同点在于该问题是循环数组，遍历到最后一个元素后要循环变量一次，因此只需要将遍历的次数改为 2 * n ，取下标改成 i % n 即可

示例代码:

func nextGreaterElements(nums []int) []int {
    n := len(nums)
    ans := make([]int, n)
    for i := range ans {
        ans[i] = -1
    }
    stk := []int{}
    for i := 0; i < 2*n; i++ {
        for len(stk) > 0 && nums[i%n] > nums[stk[len(stk)-1]] {
            top := stk[len(stk)-1]
            stk = stk[:len(stk)-1]
            ans[top] = nums[i%n]
        }
        stk = append(stk, i%n)
    }
    return ans
}

3. 接雨水

LeetCode 42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例代码：

func trap(height []int) int {
    stk := []int{}
    ans := 0
    for i := 0; i < len(height); i++ {
        for len(stk) > 0 && height[stk[len(stk)-1]] < height[i] {
            top := stk[len(stk)-1]
            stk = stk[:len(stk)-1]
            if len(stk) > 0 {
                // 弹出的栈顶元素、当前栈顶元素、当前元素构成凹槽区域
                // 高：当前元素和当前栈顶元素的较小值 - 弹出的栈顶元素
                // 宽：当前元素下标 - 当前栈顶元素下表 - 1
                ans += (min(height[i], height[stk[len(stk)-1]]) - height[top]) * (i - stk[len(stk) - 1] - 1)
            }
        }
        stk = append(stk, i)
    }
    return ans
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

4. 柱状图中最大矩形

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

该问题比 42. 接雨水 问题难的点在于要注意边界条件，为方便处理输入本身单调递增和单调递减的边界情况，在输入列表头和尾各添加一个 0。

示例代码：

func largestRectangleArea(heights []int) int {
    ans := 0
    // 头尾各加一个 0 处理边界 case
    heights = append([]int{0}, heights...)
    heights = append(heights, 0)
    stk := []int{0}
    for i := 1; i < len(heights); i++ {
        for heights[i] < heights[stk[len(stk)-1]] {
            top := stk[len(stk)-1]
            stk = stk[:len(stk)-1]
            // 高：弹出的栈顶元素
            // 宽：当前元素下标 - 当前栈顶下标 - 1
            h := heights[top]
            w := i - stk[len(stk)-1] - 1
            ans = max(ans, h*w)
        }
        stk = append(stk, i)
    }
    return ans
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

总结

使用单调栈解决算法问题的关键点有一下几点：

找到需要维护单调性的数组。通常是需要找到比当前位置大或小的元素。
根据需要维护的单调性，选择递增栈或递减栈。
确定每个元素的入栈和出栈条件。入栈条件通常是当前元素与栈顶元素的比较关系，出栈条件通常是满足当前单调性的元素。
对于每个入栈的元素，计算其对应的答案。通常是栈顶元素对应的答案，即找到比当前元素大或小的元素。
根据具体情况，确定栈中存储的是元素的下标还是元素本身。
单调栈算法通常需要先对数组进行预处理，以便在计算过程中能够快速获取需要的信息。另外，在使用单调栈解决算法问题时，需要特别注意边界条件和特殊情况的处理，以保证算法的正确性和稳定性。