每日温度&滑动窗口最大值&移掉k位数字——单调栈/单调队列模板题

# 每日温度

这道题最难想到的就是如何利用单调栈来记录状态，需要存储的实际上就是温度单调递减的数组下标，然后当碰到温度比栈顶高的值时，就可以将单调栈内的部分弹出，两个下标的差就是对应的天数了。

```go
func dailyTemperatures(temperatures []int) []int {
    n := len(temperatures)
    res := make([]int, n)
    stack := make([]int, 0, n)
    for i, v := range(temperatures) {
        for len(stack) > 0 && temperatures[stack[len(stack)-1]] < v {
            res[stack[len(stack)-1]] = i - stack[len(stack)-1]
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, i)
    }
    return res
}
```

# 滑动窗口最大值

同理，滑动窗口最大值这个题目也是类似的，需要求每个滑动窗口内的最大值，类似于每日温度需要找到后续的更高温度，都是在一个范围区间内找到目标值，只是限制不同，这里需要利用单调队列去维护一个从大到小值的下标队列，当滑动窗口向后移动且最大值的下标不在窗口内时从队头移除，然后将下一个值放入队列前需要把队尾的更小的值移除，从而就能保证队头一定是滑动窗口内的最大值。

```go
func maxSlidingWindow(nums []int, k int) []int {
    queue := make([]int, 0)
    res := make([]int, 0, len(nums)-k+1)
    for i, v := range nums {
        if len(queue) > 0 && queue[0] <= i - k {
            queue = queue[1:]
        }
        for len(queue) > 0 && nums[queue[len(queue)-1]] < v {
            queue = queue[:len(queue)-1]
        }
        queue = append(queue, i)
        if i >= k - 1 {
            res = append(res, nums[queue[0]])
        }
    }
    return res
}
```

# 移掉k位数字

这道题主要是需要推导出来删掉哪些数字才能保证最小，其实只需要靠近左边的大数尽可能被删除即可，所以我们维护一个单调栈，保证单调递增，那么就能保证删掉前面几位的大数，如果k次没用完，则从后面继续删除。

```go
func removeKdigits(num string, k int) string {
    stack := []byte{}
    for i := range num {
        for len(stack) > 0 && k > 0 && stack[len(stack)-1] > num[i] {
            stack = stack[:len(stack)-1]
            k--
        }
        stack = append(stack, num[i])
    }
    if k > 0 {
        stack = stack[:len(stack)-k]
    }
    i := 0
    for i < len(stack) && stack[i] == '0' {
        i++
    }
    if i == len(stack) {
        return "0"
    }
    return string(stack[i:])
}
```

Last modification：July 9, 2025