单调栈

理论基础

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

栈里放元素下标

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

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

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

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

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

每日温度

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

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

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

单调栈：求第一个比当前元素大的元素的距离，时间复杂度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
矩形高 = 栈顶柱子高

注意：

本题需要给原数组首尾加0，给尾加0避免给定数组递增，导致一直没有出栈计算的过程；给首加0避免给定数组递减，导致一直空栈无法计算
入栈前要循环比较当前元素与栈顶元素

 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 的数量，使用二维数组 left 记录，其中 left[i][j] 为矩阵第 i 行第 j 列元素的左边连续 1 的数量
对每一列用单调栈，对于每一列，相当于侧放的柱状图，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)

股票价格跨度

收集股票的每日报价，并返回该股票当日价格的跨度。跨度被定义为股票价格小于或等于今天价格的最大连续天数（从今天开始往回数，包括今天）。

实现 StockSpanner 类：StockSpanner() 初始化类对象。int next(int price) 给出今天的股价price ，返回该股票当日价格的跨度

思路：单调栈

栈中元素是一个二元组，一维保存股票价格，二维保存小于等于当前价格的最大连续天数，初始都是1

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


type StockSpanner struct {
    stack [][2]int
}

func Constructor() StockSpanner {
    return StockSpanner{}
}

func (this *StockSpanner) Next(price int) int {
    cnt := 1
    for len(this.stack) != 0 && price >= this.stack[len(this.stack)-1][0] {
        cnt += this.stack[len(this.stack)-1][1]
        this.stack = this.stack[:len(this.stack)-1]
    }
    this.stack = append(this.stack, [2]int{price, cnt})
    return cnt
}

移掉 K 位数字

给一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。以字符串形式返回这个最小的数字

思路：贪心+单调栈

要使剩下的数字最小，需要保证靠前的数字尽可能小

删除一个数字的贪心策略：从第二个数字遍历，每当当前数字小于前一个数字，则将前一数字删除

单调栈：当当前数字小于栈顶元素，就不断地弹出栈顶元素，直到栈空或不小于或已经删够k个数字

注意：

有单调递增情况会没删够k，这时直接从尾删剩下k即可
最后要删除前导0
若最后删完为空，则返回0

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


func removeKdigits(num string, k int) string {
    stack := []byte{}
    for _, ch := range num {
        for k > 0 && len(stack) != 0 && byte(ch) < stack[len(stack)-1] {
            k--
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, byte(ch))
    }
    // 用完剩下k
    stack = stack[:len(stack)-k]
    // 去除前导0
    res := strings.TrimLeft(string(stack), "0")
    // 判是否删完
    if res == "" {
        return "0"
    }
    return res
}

去除重复字母

316. 去除重复字母 - 力扣（LeetCode）

给一个字符串 s ，去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）

思路：贪心+单调栈

要使返回结果的字典序最小，需要保证靠前字符尽可能小

删除一个字符的贪心策略：从第二个字符遍历，每当当前字符小于前一个字符，则将前一字符删除

单调栈：当当前字符小于栈顶元素，就不断地弹出栈顶元素，直到栈空或该栈顶元素是该字符的最后一个

注意：若遍历当前字符已在栈中，则不入入栈；为此，需要记录每个字符是否在栈中出现过

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


func removeDuplicateLetters(s string) string {
    mp := map[byte]int{}
    for _, ch := range s {
        mp[byte(ch)]++
    }
    instack := map[byte]bool{}
    stack := []byte{}
    for _, ch := range s {
        if !instack[byte(ch)] {
            for len(stack) > 0 && byte(ch) < stack[len(stack)-1] && mp[stack[len(stack)-1]] > 0 {
                instack[stack[len(stack)-1]] = false
                stack = stack[:len(stack)-1]
            }
            stack = append(stack, byte(ch))
            instack[byte(ch)] = true
        }
        mp[byte(ch)]--
    }
    return string(stack)
}

拼接最大数

321. 拼接最大数 - 力扣（LeetCode）

给两个整数数组 nums1 和 nums2，长度分别为 m 和 n，代表两个数各位上的数字。同时也会得到一个整数 k。用这两个数组中的数字创建一个长度为 k <= m + n 的最大数。同一数组中数字的相对顺序必须保持不变。返回代表答案的长度为 k 的数组

思路：单调栈

要使返回结果的数字最大，需要保证靠前字符尽可能大

单调栈：遍历数组，保证栈内元素递减，且元素个数等于指定的最大子序列的长度

分治：指定nums1最大子序列的长度为i，则nums2最大子序列的长度为k-i，枚举i

归并：双指针，每次取大的，若一样大，需要看后续谁大，谁后续大取谁，若遍历结束都一样，则取长度大的（两个一样大，取谁都一样，但取长度大的，可以让长度大的下一个继续与长度小的该一样大比较）

 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59


func maxNumber(nums1 []int, nums2 []int, k int) []int {
    res := make([]int, k)
    for i := 0; i <= len(nums1) && i <= k; i++ {
        // 判nums2是否不够k-i个元素
        if k-i > len(nums2) {
            continue
        }
        // 分治：枚举i得到nums1的i个最大, 得到nums2的k-i个最大
        numsM1 := getMax(nums1, i)
        numsM2 := getMax(nums2, k-i)
        // 归并
        numsMerged := merge(numsM1, numsM2)
        // 比较字典序更新结果
        if isBigger(numsMerged, res) {
            res = numsMerged
        }
    }
    return res
}

// 得到最大子序列
func getMax(nums []int, cnt int) []int {
    stack := []int{}
    // 栈中元素的可删除次数
    delCnt := len(nums) - cnt
    for _, v := range nums {
        for len(stack) > 0 && delCnt > 0 && v > stack[len(stack)-1] {
            stack = stack[:len(stack)-1]
            delCnt--
        }
        stack = append(stack, v)
    }
    return stack[:cnt]
}

// 合并两个最大子序列
func merge(nums1, nums2 []int) []int {
    res := make([]int, len(nums1)+len(nums2))
    for i := range res {
        if isBigger(nums1, nums2) {
            res[i] = nums1[0]
            nums1 = nums1[1:]
        } else {
            res[i] = nums2[0]
            nums2 = nums2[1:]
        }
    }
    return res
}

// 比较字典序
func isBigger(nums1, nums2 []int) bool {
    for i := 0; i < len(nums1) && i < len(nums2); i++ {
        if nums1[i] != nums2[i] {
            return nums1[i] > nums2[i]
        }
    }
    return len(nums1) > len(nums2)
}

时间复杂度：O(k(m+n+k^2))，其中 m 和 n 分别是数组 nums1 和 nums2的长度，k 是拼接最大数的长度
空间复杂度：O(k)