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


栈里边存放的是还没有找到后边更大值的元素

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
// 从左向右，
func dailyTemperatures(temperatures []int) []int {
    length := len(temperatures)  // 长度 
    ans := make([]int, length)   // 返回的数组
    stack := []int{}            // 单调栈
    for i := 0; i < length; i ++ {
        temperature := temperatures[i] 
        fmt.Println("temperature:", temperature)
        fmt.Println("stack:", stack)
        for len(stack) > 0 && temperature > temperatures[stack[len(stack) -1]] {
            fmt.Println("temperature now:", temperature, temperatures[stack[len(stack) -1]], stack[len(stack) -1])
            preindex := stack[len(stack)-1] // 上一个位置的index
            stack = stack[:len(stack) -1] // 栈顶找到了当前更大的数，
            ans[preindex] = i -preindex // 记录位置
        }
        stack = append(stack, i) // 如果不满足要求，则说明是小的数，需要添加到栈中
    }
    return ans
}


// 从右向左

func dailyTemperatures(temperatures []int) []int {
    lens := len(temperatures)
    ans := make([]int, lens)
    stack := []int{}  // 单调递增栈（从栈底到栈顶）
    
    for i := lens-1; i >= 0; i-- {
        temperature := temperatures[i]
        // 弹出所有小于等于当前温度的索引
        for len(stack) > 0 && temperature >= temperatures[stack[len(stack)-1]] {
            stack = stack[:len(stack)-1]
        }
        // 如果栈不为空，栈顶就是第一个比当前大的温度
        if len(stack) > 0 {
            ans[i] = stack[len(stack)-1] - i
        }
        stack = append(stack, i)
    }
    return ans
}




单调栈 适用于 上一个更大(更小)元素，或者下一个更大（小）元素

这段代码是一个Go语言编写的函数，名为dailyTemperatures，它使用单调栈的数据结构来解决一个特定问题：给定一个每日温度列表temperatures，返回一个新列表，其中第i个元素是温度列表中第i天之后第一个比第i天温度更高的温度的天数。

代码思想解释：

  1. 问题定义：我们想要找到一个序列中每个元素之后的第一个更大元素，并记录它们之间的索引差。

  2. 单调栈的应用：单调栈是一种特殊的栈结构，它保证栈内的元素是单调递增或单调递减的。在这个场景中，我们使用单调栈来维护一个索引栈，栈内元素代表尚未找到更大温度的天的索引。

  3. 初始化：

    • n：记录输入温度数组的长度。
    • ans：初始化一个长度为n的数组，用于存储结果，初始值设为0。
    • st：初始化一个空的切片，用作单调栈。

  4. 遍历温度数组：

    • 通过range关键字遍历temperatures数组，同时获取索引i和对应的温度值t。

  5. 维护单调栈：

    • 当前温度t大于栈顶元素对应的温度时，说明栈顶元素之后的第一个更高温度就是当前温度。此时，执行以下操作：
      • 弹出栈顶元素j，即st[len(st)-1]。
      • 计算索引差i - j，并将这个差值赋给ans[j]。
      • 更新栈st，移除栈顶元素。

  6. 压栈操作：

    • 将当前索引i压入栈st中。这表示当前索引的天还没有找到之后的第一个更高温度。

  7. 返回结果：

    • 遍历结束后，返回ans数组，其中每个元素表示对应天之后第一个更高温度的天数。

接雨水

42. 接雨水 - 力扣（LeetCode）

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

func trap(height []int) (ans int) {
    st := []int{}
    for i, h := range height {
        for len(st) > 0 && h >= height[st[len(st)-1]] { // 1. **处理相等高度的情况**：
%%     
    - 当遇到相等高度的柱子时，后面的柱子才是有效的右边界
        
    - 使用`>=`可以正确处理这种情况，确保弹出所有小于等于当前高度的柱子
        
    - 如果只用`>`，相等高度的柱子会留在栈中，导致计算错误 %%
            bottomH := height[st[len(st)-1]]
            st = st[:len(st)-1]
            if len(st) == 0 {
                break
            }
            left := st[len(st)-1]
            dh := min(height[left], h) - bottomH // 面积的高
            ans += dh * (i - left - 1)// 面积高*宽
        }
        st = append(st, i)
    }
    return
}

## 示例分析

以高度数组`[0,1,0,2,1,0,1,3,2,1,2,1]`为例：

1. 遇到第二个高度为1的柱子时：
    
    - 弹出之前高度为0的柱子
        
    - 计算它与左边高度1的柱子之间的雨水
        
2. 遇到高度为2的柱子时：
    
    - 弹出高度为1的柱子（因为2 >= 1）
        
    - 计算它与左边更高柱子之间的雨水
        
3. 遇到相等高度1的柱子时：
    
    - 前面的1被弹出（因为1 >= 1）
        
    - 确保新的1作为右边界参与后续计算

单调队列

239. 滑动窗口最大值

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

func maxSlidingWindow(nums []int, k int) []int {
    ans := make([]int, 0, len(nums)-k+1) // 预分配空间
    q := []int{}
    for i, x := range nums {
        // 1. 入
        for len(q) > 0 && x >= nums[q[len(q)-1]] {
            q = q[:len(q)-1] // 维护 q 的单调性 从大到小
        }
        q = append(q, i)

        // 2. 出
        if q[0] <= i -k{ // 队首已经离开窗口了
            q = q[1:] // Go 的切片是 O(1) 的
        }

        // 3. 记录答案
        if i >= k-1 {
            // 由于队首到队尾单调递减，所以窗口最大值就是队首
            ans = append(ans, nums[q[0]])
        }
    }
    return ans
}

从「维护单调性」的角度上来说，单调队列和单调栈是一样的，一个弹出队尾元素，另一个弹出栈顶元素。在单调栈的基础上，单调队列多了一个「移除队首」的操作，这类似滑动窗口移动左指针 left 的过程。所以从某种程度上来说，单调队列 = 单调栈 + 滑动窗口。