返回
Algorithm 基础能力

单调栈

理论基础

单调栈适合于找第一个比当前元素大或者小的

栈里放元素下标

栈顶到栈底递增：求第一个比当前元素大的；栈顶到栈底递减：求第一个比当前元素小的

求第一个比当前元素大的工作过程：遍历数组

  • 当前遍历元素比栈顶大：说明栈顶元素找到了第一个比大的，用一个新数组（结果集）记录下来，新数组的下标用当前栈顶保存的下标，若是求距离，数组值就用当前遍历元素下标减去栈顶保存的下标；栈顶弹出，继续比较，看当前元素是否是栈中其他元素遇到的第一个比它大的元素，直到当前元素比栈顶元素小时则入栈；
  • 当前遍历元素比栈顶小：直接入栈
  • 当前遍历元素等于栈顶：题目是求大于，则直接入栈；若题目是求大于等于则记录、弹栈、入栈
  • 最后结果集中数组值是数组下标所对应元素的第一个比它大的元素的距离，栈中剩下的是没有找到比该元素大的元素

单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是整个数组只需要遍历一次。

更直白来说，就是用一个栈来记录我们遍历过的元素，因为我们遍历数组的时候，我们不知道之前都遍历了哪些元素，以至于遍历一个元素找不到是不是之前遍历过一个更小的，所以我们需要用一个容器（这里用单调栈）来记录我们遍历过的元素。

每日温度

739. 每日温度 - 力扣（LeetCode）

给定一个数组，每个元素表示每天的温度，返回一个数组，每个元素表示比该天温度高的下一温度出现在第几天，若没有则为0

暴力超时：两层for循环，外层i循环遍历每天温度，内层j从i+1开始循环从找高温，时间复杂度O(n2)

单调栈：求第一个比当前元素大的元素的距离，时间复杂度O(n)

  • 定义一个结果数组；go中用切片模拟栈，push：append，pop：[:len(stack)-1]
  • 进入循环前将下标0元素入栈；外层for循环从下标1遍历给定数组；若当前元素小于等于栈顶元素，则入栈；若栈非空且当前元素大于栈顶，则记录（结果集的下标用栈顶下标）、弹栈
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func dailyTemperatures(temperatures []int) []int {
    res := make([]int, len(temperatures))
    stack := make([]int, 0)
    stack = append(stack, 0)
    for i := 1; i < len(temperatures); i++ {
        if temperatures[i] <= temperatures[stack[len(stack)-1]] {
            stack = append(stack, i)
        } else {
            for len(stack) != 0 && temperatures[i] > temperatures[stack[len(stack)-1]] {
                res[stack[len(stack)-1]] = i - stack[len(stack)-1]
                stack = stack[:len(stack)-1]
            }
            stack = append(stack, i)
        }
    }
    return res
}

精简版：用for range从首遍历，内层若栈非空且比栈顶大，则记录、弹栈；最后当前元素下标入栈

注意：

  • 栈初始化容量为0
  • 进入循环前不需要首元素入栈，因为进入循环后判断栈空时会入栈
  • 要用for循环判断当前元素与栈顶元素，不能用if只判断一次
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func dailyTemperatures(temperatures []int) []int {
    res := make([]int, len(temperatures))
    stack := make([]int, 0)
    for i, v := range temperatures {
        for len(stack) != 0 && v > temperatures[stack[len(stack)-1]] {
            res[stack[len(stack)-1]] = i - stack[len(stack)-1]
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, i)
    }
    return res
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

下一个更大元素 I

496. 下一个更大元素 I - 力扣（LeetCode）

给定两个整数数组nums1和nums2，nums1是nums2的子集，求nums1中每个元素值在nums2中对应元素值右侧第一个比该元素值大的元素值，若没有比该元素值大的则为-1

结果数组初始化长度为nums1长度，值全为-1

map映射：遍历nums1；元素值作为K，下标作为V

单调栈：遍历nums2，若当前元素比栈顶元素大，判断在map中能否找到栈顶元素，能找到则记录（map中v作为结果数组下标，当前元素值作为结果数组值），最后弹栈、循环比较、入栈

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func nextGreaterElement(nums1 []int, nums2 []int) []int {
    res := make([]int, len(nums1))
    stack := make([]int, 0)
    mapping := make(map[int]int)
    for i := range res {
        res[i] = -1
    }
    for i, v := range nums1 {
        mapping[v] = i
    }
    for _, cur := range nums2 {
        for len(stack) != 0 && cur > stack[len(stack)-1] {
            if v, ok := mapping[stack[len(stack)-1]]; ok {
                res[v] = cur
            }
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, cur)
    }
    return res
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

下一个更大元素 II

503. 下一个更大元素 II - 力扣（LeetCode）

给定一个循环数组，返回数组中每个元素的下一个比它大的元素，没找到就是-1

循环遍历也就是从当前元素开始向后遍历到尾后，再从首开始向后遍历到当前元素，即遍历两遍该数组

思路一：用两个数组拼接后的新数组模拟成环遍历，结果集初始化为新数组长度，最后返回结果集的前半部分

思路二：遍历次数为二倍数组长度，循环变量取模，下标对数组长度取模

注意：go中追加切片时需要将切片用...打散

思路一：构建新数组

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func nextGreaterElements(nums []int) []int {
    nums = append(nums, nums...)
    res := make([]int, len(nums))
    stack := make([]int, 0)
    for i := range res {
        res[i] = -1
    }
    for i, cur := range nums {
        for len(stack) != 0 && cur > nums[stack[len(stack)-1]] {
            res[stack[len(stack)-1]] = cur
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, i)
    }
    return res[:len(res)/2]
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

思路二：取模

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func nextGreaterElements(nums []int) []int {
    res := make([]int, len(nums))
    stack := make([]int, 0)
    for i := range res {
        res[i] = -1
    }
    for i := 0; i < len(nums)*2; i++ {
        for len(stack) != 0 && nums[i%len(nums)] > nums[stack[len(stack)-1]] {
            res[stack[len(stack)-1]] = nums[i%len(nums)]
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, i%len(nums))
    }
    return res
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

接雨水

42. 接雨水 - 力扣（LeetCode）

给定一个整数数组，表示横轴上每个宽度为一的柱子的高度，雨水从上落下，返回这些柱子之间的凹槽能接到的最大雨水量，纵轴不算柱子，可以落到横轴上

遍历柱子，求出每个柱子左边和右边第一个比它高的柱子的高度

  • 栈顶下标元素的柱子的凹槽能接的雨水量的高度 = min（左柱子高度，右柱子高度）- 栈顶下标元素的柱子高度；
  • 栈顶下标元素的柱子的凹槽能接的雨水量的宽度 = 右柱子下标 - 左柱子下标 - 1

单调栈是横向从下往上求雨水面积

注意：一旦有弹栈操作，后面对栈操作前都要判断栈是否非空

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func trap(height []int) int {
    res := 0
    stack := make([]int, 0)
    for i, v := range height {
        for len(stack) != 0 && v > height[stack[len(stack)-1]] {
            mid := height[stack[len(stack)-1]]
            stack = stack[:len(stack)-1]
            if len(stack) != 0 {
                h := min(v, height[stack[len(stack)-1]]) - mid
                w := i - stack[len(stack)-1] - 1
                res += h * w
            }
        }
        stack = append(stack, i)
    }
    return res
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

柱状图中最大的矩形

84. 柱状图中最大的矩形 - 力扣（LeetCode）

给定一个整数数组，数组中各个元素表示柱状图中各个柱子的高度，每个柱子彼此相邻且宽度为 1 ，求在该柱状图中，能够勾勒出来的矩形的最大面积，可以是多个相邻柱子组成的矩形面积，也可以是单个柱子面积

用当前柱子的左右第一个小值的坐标逼出当前柱子自身横向扩展的最大值：每一个柱子都去找左右边比它矮的第一个柱子来确定宽，再用该柱子的高乘以宽，就能算出该柱子所能形成的最大矩形面积，最后返回一个最大的即可

递增单调栈：若当前元素大于等于栈顶元素，则入栈；若当前元素小于栈顶元素，则说明找到了栈顶元素右边第一个比它小的元素，记录栈顶元素后出栈，新栈顶元素是出栈元素左边第一个小于等于它的元素

  • 矩形宽 = 右边柱子下标 - 左边柱子下标 - 1
  • 矩形高 = 栈顶柱子高

注意：

  1. 本题需要给原数组首尾加0，给尾加0避免给定数组递增，导致一直没有出栈计算的过程；给首加0避免给定数组递减，导致一直空栈无法计算
  2. 入栈前要循环比较当前元素与栈顶元素
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func largestRectangleArea(heights []int) int {
    res := 0
    heights = append([]int{0}, heights...)
    heights = append(heights, 0)
    stack := make([]int, 0)
    for i, v := range heights {
        for len(stack) != 0 && v < heights[stack[len(stack)-1]] {
            mid := heights[stack[len(stack)-1]]
            stack = stack[:len(stack)-1]
            if len(stack) != 0 {
                w := i - stack[len(stack)-1] - 1
                res = max(res, w*mid)
            }
        }
        stack = append(stack, i)
    }
    return res
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

最大矩形

85. 最大矩形 - 力扣（LeetCode）

给定一个只包含0和1矩阵，返回只含1的最大矩形面积

思路：

  1. 将输入拆分成一系列的柱状图：计算出矩阵的每个元素的左边连续 1 的数量，使用二维数组 left 记录，其中 left[i][j] 为矩阵第 i 行第 j 列元素的左边连续 1 的数量
  2. 对每一列用单调栈，对于每一列，相当于侧放的柱状图，left中元素值即为柱的高度

注意：首尾加0防单调

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

func maximalRectangle(matrix [][]byte) int {
    // 首尾加0防单调
    tempRow := make([][]byte, 1)
    tempRow[0] = make([]byte, len(matrix[0]))
    matrix = append(tempRow, matrix...)
    matrix = append(matrix, tempRow...)
    // 将输入处理成柱状图:计算每个元素左边连续1的数量
    left := make([][]int, len(matrix))
    for i := range matrix {
        left[i] = make([]int, len(matrix[i]))
        for j, v := range matrix[i] {
            // 判当前元素是否为1
            if v == '1' {
                // 判是否首列
                if j == 0 {
                    left[i][0] = 1
                } else {
                    // 在左基础上加一
                    left[i][j] = left[i][j-1] + 1
                }
            }
        }
    }
    res := 0
    // 从左往右遍历所有列
    for j := 0; j < len(matrix[0]); j++ {
        stack := make([]int, 0)
        // 对该列从上往下遍历
        for i := 0; i < len(matrix); i++ {
            for len(stack) != 0 && left[i][j] < left[stack[len(stack)-1]][j] {
                height := left[stack[len(stack)-1]][j]
                stack = stack[:len(stack)-1]
                if len(stack) != 0 {
                    w := i - stack[len(stack)-1] - 1
                    res = max(res, w*height)
                }
            }
            stack = append(stack, i)
        }
    }
    return res
}
  • 时间复杂度：O(mn)
  • 空间复杂度：O(n)
© 2021 - 2024 YI · 0 Days
共叭叭了 2159731字 · 173篇文章

Built with Hugo
Theme Stack designed by Jimmy