My-Notes

Search

SearchSearch

036.单调队列-上

Dec 29, 2023, 10 min read

前置知识：用数组方式实现队列、滑动窗口

单调队列

最经典的用法是解决如下问题

滑动窗口在滑动时，r++ 代表右侧数字进窗口，l++ 代表左侧数字出窗口

这个过程中，想随时得到当前滑动窗口的最大值或者最小值

思路

以获取最大值为例

r++ 时：从队尾入队，看当前将要入队元素是否大于队尾元素，如果大则依次将队尾元素出队，直到当前将要入队的元素不再比队尾元素大或队空，则停止

var idx int // 当前将要入队的元素的索引
 
// 队不空，并且当前将要入队的元素大于队尾元素，则队尾元素出队
// 当前元素要入队，队列中不比当前元素大，那么它就不可能成为最大值了，出队！
for len(queue) > 0 && arr[idx] > arr[queue[len(queue)-1]] {
	queue = queue[:len(queue)-1] // 队尾元素出队
}
 
// 当前将要入队的元素入队
queue = append(queue, idx)

l++ 时：看队头，如果队头元素是当前将要出队的元素，则队头元素从队头出队

var idx int // 当前将要出队元素的索引
 
// 如果队头元素是当前将要出队的元素，队头元素就从队头出队
// 下一个元素成了最大值（队头 -> 队尾：大 -> 小）
if queue[0] == idx {
	queue = queue[1:] // 队头元素从队头出队
}

整个过程中，队头元素（queue[0]）一直是滑动窗口的最大值

单调双端队列：维持了依次成为最大值的可能性（随着 l++ 可能成为最大值就留在单调队列中，不可能成为最大值就出队）

复杂度

窗口滑动的过程中，单调队列所有调整的总代价为 ，单次操作的均摊代价为 ，因为所有元素均只入队出队一次

空间复杂度：，单调双端队列的空间

备注

这是单调队列最经典的用法，可以解决很多题目，下节课将继续介绍其他的用法

单调队列可以和很多技巧交叉使用！比如：动态规划 + 单调队列优化，会在【扩展】课程里讲述

题目1.单调队列最经典用法的模版

题目描述

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3

输出：[3,3,5,5,6,7]

解释：

滑动窗口的位置                    最大值
---------------                 -----
[1  3  -1] -3  5  3  6  7        3
 1 [3  -1  -3] 5  3  6  7        3
 1  3 [-1  -3  5] 3  6  7        5
 1  3  -1 [-3  5  3] 6  7        5
 1  3  -1  -3 [5  3  6] 7        6
 1  3  -1  -3  5 [3  6  7]       7

提示：

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • 1 <= k <= nums.length

测试链接

239.滑动窗口最大值

答案

单调队列

题目2.绝对差不超过限制的最长子数组

题目描述

给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit。

如果不存在满足条件的子数组，则返回 0。

提示：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 0 <= limit <= 10^9

测试链接

1438.绝对差不超过限制的最长连续子数组

思路

子数组中任意两元素之间的绝对差 = 子数组最大值 - 子数组最小值

当子数组变长时，最大值可能变大，最小值可能变小，即绝对差可能变大或不变，绝不可能变小

所以当一个子数组满足要求时（任意两元素的绝对差 <= limit），缩短子数组也满足要求；当一个子数组不满足要求时，增长子数组也不满足要求

答案

const (
	MAXN = 1e5 + 1
)
 
var (
	arr        []int
	maxDeque   = [MAXN]int{} // 维持窗口最大值的单调队列
	maxH, maxT = 0, 0
	minDeque   = [MAXN]int{} // 维持窗口最小值的单调队列
	minH, minT = 0, 0
)
 
func longestSubarray(nums []int, limit int) int {
	maxH, maxT = 0, 0
	minH, minT = 0, 0
	arr = nums
	n := len(nums)
	ans := 0
	r := 0
	for l := 0; l < n; l++ {
		// [l,r)，r 是没有进入窗口的、下一个数所在的位置
		for r < n && ok(limit, nums[r]) {
			push(r)
			r++
		}
		// 从循环出来：[l,r) 是 l 开头的子数组能向右延伸的最大范围
		ans = max(ans, r-l)
		pop(l)
	}
	return ans
}
 
// 判断如果加入 num，窗口最大值 - 窗口最小值是否 <= limit
func ok(limit, num int) bool {
	// 如果 num 进来，新窗口的最大值
	maxx := num
	if maxH < maxT { // mexDeque 有元素
		maxx = max(maxx, arr[maxDeque[maxH]])
	}
	// 如果 num 进来，新窗口的最小值
	minn := num
	if minH < minT {
		minn = min(minn, arr[minDeque[minH]])
	}
 
	return maxx-minn <= limit
}
 
// idx 进入滑动窗口，维持两个单调队列正确
func push(idx int) {
	for maxH < maxT && arr[maxDeque[maxT-1]] <= arr[idx] {
		maxT--
	}
	maxDeque[maxT] = idx
	maxT++
	for minH < minT && arr[minDeque[minT-1]] >= arr[idx] {
		minT--
	}
	minDeque[minT] = idx
	minT++
}
 
// 滑动窗口吐出 idx，维持两个单调队列正确
func pop(idx int) {
	if maxH < maxT && maxDeque[maxH] == idx {
		maxH++
	}
	if minH < minT && minDeque[minH] == idx {
		minH++
	}
}

复杂度

  • 时间复杂度：，滑动窗口 + 单调队列
  • 空间复杂度：，两个单调队列

题目3.接取落水的最小花盆

题目描述

老板需要你帮忙浇花。给出 N 滴水的坐标，y 表示水滴的高度，x 表示它下落到 x 轴的位置

每滴水以每秒 1 个单位长度的速度下落。你需要把花盆放在 x 轴上的某个位置

使得从被花盆接着的第 1 滴水开始，到被花盆接着的最后 1 滴水结束，之间的时间差至少为 D

我们认为，只要水滴落到 x 轴上，与花盆的边沿对齐，就认为被接住

给出 N 滴水的坐标和 D 的大小，请算出最小的花盆的宽度 W

测试链接

P2698 Flowerpot S

思路

基本同 题目2

答案

package main
 
import (
	"bufio"
	"fmt"
	"math"
	"os"
	"sort"
	"strconv"
)
 
const (
	MAXN    = 100005
	MAX_INT = math.MaxInt
)
 
var (
	n          int
	d          int
	arr        = [MAXN][2]int{} // [x, y]
	maxDeque   = [MAXN]int{}
	maxH, maxT = 0, 0
	minDeque   = [MAXN]int{}
	minH, minT = 0, 0
)
 
func main() {
	in := bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	for in.Scan() {
		n, _ = strconv.Atoi(in.Text())
		in.Scan()
		d, _ = strconv.Atoi(in.Text())
		for i := 0; i < n; i++ {
			in.Scan()
			arr[i][0], _ = strconv.Atoi(in.Text())
			in.Scan()
			arr[i][1], _ = strconv.Atoi(in.Text())
		}
		ans := compute()
		if ans == MAX_INT {
			fmt.Fprintln(out, -1)
		} else {
			fmt.Fprintln(out, ans)
		}
	}
	out.Flush()
}
 
func compute() int {
	maxH, maxT = 0, 0
	minH, minT = 0, 0
	sort.Slice(arr[:n], func(i, j int) bool {
		return arr[i][0] < arr[j][0]
	})
	ans := MAX_INT
	r := 0
	for l := 0; l < n; l++ {
		// [l,r)
		for r < n && !ok() {
			push(r)
			r++
		}
		if ok() {
			ans = min(ans, arr[r-1][0]-arr[l][0])
		}
		pop(l)
	}
	return ans
}
 
// 当前窗口最大值 - 最小值 >= d
func ok() bool {
	maxx := 0
	if maxH < maxT {
		maxx = arr[maxDeque[maxH]][1]
	}
	minn := 0
	if minH < minT {
		minn = arr[minDeque[minH]][1]
	}
	return maxx-minn >= d
}
 
func push(idx int) {
	for maxH < maxT && arr[maxDeque[maxT-1]][1] <= arr[idx][1] {
		maxT--
	}
	maxDeque[maxT] = idx
	maxT++
	for minH < minT && arr[minDeque[minT-1]][1] >= arr[idx][1] {
		minT--
	}
	minDeque[minT] = idx
	minT++
}
 
func pop(idx int) {
	if maxH < maxT && maxDeque[maxH] == idx {
		maxH++
	}
	if minH < minT && minDeque[minH] == idx {
		minH++
	}
}

Graph View

Backlinks