抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

特性

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

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

算法应用

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

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

具体的实现步骤如下:

  1. 遍历数组 nums,依次将元素入栈
  2. 当栈顶元素小于当前元素时,弹出栈顶元素,将其下一个更大元素设为当前元素,并继续弹出栈顶元素,直到栈为空或栈顶元素大于等于当前元素
  3. 当遍历完数组后,栈中剩余的元素的下一个更大元素均为-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
}

总结

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

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

评论