algorithm

发布日期: 2023-07-28

更新日期: 2025-12-06

文章字数: 2.3k

阅读时长: 9 分

单调栈简介

单调栈（Monotone Stack）是一种特殊的栈数据结构，栈内元素（从栈底到栈顶）保持单调递增或单调递减的性质。

单调栈的核心思想是：在维护栈的单调性的同时，利用出栈操作来解决问题。当新元素入栈时，会将所有破坏单调性的栈顶元素出栈，并且出栈的元素不会再次入栈。由于每个元素只有一次入栈和出栈的操作，所以单调栈的维护时间复杂度是 O(n)。

基本性质

单调栈具有以下两个重要性质：

单调性：栈内元素保持单调递增或单调递减。
查找性质：
- 递增栈（栈底到栈顶递增）：可以找到元素左右两侧第一个比自身小的元素
- 递减栈（栈底到栈顶递减）：可以找到元素左右两侧第一个比自身大的元素

工作原理

递增栈示例

以递增栈为例（假设所有元素都是唯一的），当新元素入栈时：

对于出栈元素：找到右侧第一个比自身小的元素（即新入栈的元素）
对于新元素：等待所有破坏递增顺序的元素出栈后，栈顶元素就是左侧第一个比自身小的元素

示例过程

假设数组 [3, 1, 4, 2, 5]，使用递增栈：

初始: stack = []
元素 3: stack = [3]
元素 1: 3 > 1，3出栈（3的右侧第一个小元素是1），stack = [1]
元素 4: 1 < 4，4入栈，stack = [1, 4]
元素 2: 4 > 2，4出栈（4的右侧第一个小元素是2），stack = [1, 2]
元素 5: 2 < 5，5入栈，stack = [1, 2, 5]

递减栈示例

以递减栈为例，当新元素入栈时：

对于出栈元素：找到右侧第一个比自身大的元素（即新入栈的元素）
对于新元素：等待所有破坏递减顺序的元素出栈后，栈顶元素就是左侧第一个比自身大的元素

Golang 实现

基础单调栈实现

package main

import "fmt"

// 递增栈：找到每个元素右侧第一个比它小的元素
func nextSmallerElement(nums []int) []int {
    n := len(nums)
    result := make([]int, n)
    stack := make([]int, 0) // 存储索引
    
    // 初始化结果数组为-1（表示没有找到）
    for i := range result {
        result[i] = -1
    }
    
    for i := 0; i < n; i++ {
        // 维护递增栈：当前元素小于栈顶元素时，栈顶元素出栈
        for len(stack) > 0 && nums[stack[len(stack)-1]] > nums[i] {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            result[top] = nums[i] // 找到右侧第一个比它小的元素
        }
        stack = append(stack, i)
    }
    
    return result
}

// 递减栈：找到每个元素右侧第一个比它大的元素
func nextGreaterElement(nums []int) []int {
    n := len(nums)
    result := make([]int, n)
    stack := make([]int, 0)
    
    for i := range result {
        result[i] = -1
    }
    
    for i := 0; i < n; i++ {
        // 维护递减栈：当前元素大于栈顶元素时，栈顶元素出栈
        for len(stack) > 0 && nums[stack[len(stack)-1]] < nums[i] {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            result[top] = nums[i] // 找到右侧第一个比它大的元素
        }
        stack = append(stack, i)
    }
    
    return result
}

func main() {
    nums := []int{3, 1, 4, 2, 5}
    
    fmt.Println("原数组:", nums)
    fmt.Println("右侧第一个小元素:", nextSmallerElement(nums))
    fmt.Println("右侧第一个大元素:", nextGreaterElement(nums))
    
    // 输出:
    // 原数组: [3 1 4 2 5]
    // 右侧第一个小元素: [1 -1 2 -1 -1]
    // 右侧第一个大元素: [4 4 5 5 -1]
}

找到左右两侧的边界

// 找到每个元素左侧和右侧第一个比它小的元素
func findBoundaries(nums []int) (left, right []int) {
    n := len(nums)
    left = make([]int, n)  // 左侧第一个小元素的索引
    right = make([]int, n) // 右侧第一个小元素的索引
    stack := make([]int, 0)
    
    // 初始化
    for i := range left {
        left[i] = -1
        right[i] = n
    }
    
    // 找到右侧边界
    for i := 0; i < n; i++ {
        for len(stack) > 0 && nums[stack[len(stack)-1]] > nums[i] {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            right[top] = i // 右侧第一个小元素的索引
        }
        stack = append(stack, i)
    }
    
    // 清空栈，找到左侧边界
    stack = stack[:0]
    for i := n - 1; i >= 0; i-- {
        for len(stack) > 0 && nums[stack[len(stack)-1]] > nums[i] {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            left[top] = i // 左侧第一个小元素的索引
        }
        stack = append(stack, i)
    }
    
    return left, right
}

常见应用场景

1. 每日温度问题

问题描述：给定一个温度数组，找到每一天之后需要等待多少天才能遇到更高的温度。

// LeetCode 739. 每日温度
func dailyTemperatures(temperatures []int) []int {
    n := len(temperatures)
    result := make([]int, n)
    stack := make([]int, 0) // 存储索引，递减栈
    
    for i := 0; i < n; i++ {
        // 当前温度大于栈顶温度，栈顶元素出栈
        for len(stack) > 0 && temperatures[stack[len(stack)-1]] < temperatures[i] {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            result[top] = i - top // 计算等待天数
        }
        stack = append(stack, i)
    }
    
    return result
}

func main() {
    temps := []int{73, 74, 75, 71, 69, 72, 76, 73}
    result := dailyTemperatures(temps)
    fmt.Println("温度数组:", temps)
    fmt.Println("等待天数:", result)
    // 输出: [1 1 4 2 1 1 0 0]
}

2. 下一个更大元素

问题描述：找到数组中每个元素右侧第一个比它大的元素。

// LeetCode 496. 下一个更大元素 I
func nextGreaterElement(nums []int) []int {
    n := len(nums)
    result := make([]int, n)
    stack := make([]int, 0)
    
    for i := range result {
        result[i] = -1
    }
    
    for i := 0; i < n; i++ {
        for len(stack) > 0 && nums[stack[len(stack)-1]] < nums[i] {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            result[top] = nums[i]
        }
        stack = append(stack, i)
    }
    
    return result
}

3. 柱状图中最大的矩形

问题描述：给定 n 个非负整数，用来表示柱状图中各个柱子的高度。求在该柱状图中，能够勾勒出来的矩形的最大面积。

// LeetCode 84. 柱状图中最大的矩形
func largestRectangleArea(heights []int) int {
    n := len(heights)
    stack := make([]int, 0)
    maxArea := 0
    
    for i := 0; i <= n; i++ {
        // 在最后添加一个高度为0的柱子，确保所有柱子都能被处理
        var h int
        if i < n {
            h = heights[i]
        } else {
            h = 0
        }
        
        // 维护递增栈
        for len(stack) > 0 && heights[stack[len(stack)-1]] > h {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            
            // 计算以 heights[top] 为高的矩形面积
            width := i
            if len(stack) > 0 {
                width = i - stack[len(stack)-1] - 1
            }
            area := heights[top] * width
            if area > maxArea {
                maxArea = area
            }
        }
        stack = append(stack, i)
    }
    
    return maxArea
}

func main() {
    heights := []int{2, 1, 5, 6, 2, 3}
    fmt.Println("柱状图高度:", heights)
    fmt.Println("最大矩形面积:", largestRectangleArea(heights))
    // 输出: 10
}

4. 接雨水问题

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

// LeetCode 42. 接雨水
func trap(height []int) int {
    stack := make([]int, 0) // 存储索引，递减栈
    water := 0
    
    for i := 0; i < len(height); i++ {
        // 当前高度大于栈顶高度，形成凹槽
        for len(stack) > 0 && height[stack[len(stack)-1]] < height[i] {
            bottom := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            
            if len(stack) == 0 {
                break
            }
            
            // 计算雨水面积
            left := stack[len(stack)-1]
            width := i - left - 1
            h := min(height[left], height[i]) - height[bottom]
            water += width * h
        }
        stack = append(stack, i)
    }
    
    return water
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func main() {
    height := []int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}
    fmt.Println("高度数组:", height)
    fmt.Println("接水量:", trap(height))
    // 输出: 6
}

5. 最大矩形

问题描述：给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

// LeetCode 85. 最大矩形
func maximalRectangle(matrix [][]byte) int {
    if len(matrix) == 0 {
        return 0
    }
    
    m, n := len(matrix), len(matrix[0])
    heights := make([]int, n)
    maxArea := 0
    
    for i := 0; i < m; i++ {
        // 计算每一行的柱状图高度
        for j := 0; j < n; j++ {
            if matrix[i][j] == '1' {
                heights[j]++
            } else {
                heights[j] = 0
            }
        }
        // 对每一行使用柱状图最大矩形算法
        area := largestRectangleArea(heights)
        if area > maxArea {
            maxArea = area
        }
    }
    
    return maxArea
}

时间复杂度分析

时间复杂度：O(n)，每个元素最多入栈一次、出栈一次
空间复杂度：O(n)，最坏情况下栈中存储所有元素

使用技巧

选择递增栈还是递减栈：
- 需要找第一个更小的元素 → 使用递增栈
- 需要找第一个更大的元素 → 使用递减栈
存储索引还是值：
- 通常存储索引，因为索引可以同时获取值和位置信息
- 如果只需要值，也可以直接存储值
处理边界情况：
- 数组为空或只有一个元素
- 所有元素都相同的情况
- 需要处理重复元素时，可能需要存储索引对
循环数组处理：
- 对于循环数组，可以将数组扩展为两倍长度，或者使用取模运算

总结

单调栈是一种非常实用的数据结构，特别适合解决”找到第一个更大/更小元素”这类问题。其核心思想是通过维护栈的单调性，在元素出栈时解决问题。掌握单调栈的关键在于：

理解递增栈和递减栈的区别
理解出栈操作的含义（找到边界）
熟练应用在各类问题中

参考文献

LeetCode 单调栈专题
《算法导论》
Go 语言算法与数据结构

djaigo

https://blog.djaigo.com/algorithm/dan-diao-zhan.html

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 djaigo !

golang algorithm

MySQL 日志详解

2023-07-28 mysql

mysql database log

linux-sed命令

2023-03-31 linux

shell

单调栈

单调栈简介

基本性质

工作原理

递增栈示例

示例过程

递减栈示例

Golang 实现

基础单调栈实现

找到左右两侧的边界

常见应用场景

1. 每日温度问题

2. 下一个更大元素

3. 柱状图中最大的矩形

4. 接雨水问题

5. 最大矩形

时间复杂度分析

使用技巧

总结

参考文献

程序猿唯一赚钱方式!<br/>The only way to make money for code monkey!