037.单调队列-下

前置知识：单调队列-上

除了单调队列最经典的用法之外，在很多问题里单调队列还可以维持求解答案的可能性

1. 单调队列里的所有对象按照规定好的单调性来组织
2. 当某个对象从队尾进入单调队列时，会从队头或者队尾依次淘汰单调队列里，对后续求解答案没有帮助的对象
3. 每个对象一旦从单调队列弹出，可以结算此时这个对象参与的答案，随后这个对象不再参与后续求解答案的过程
4. 其实是先有对题目的分析！进而发现单调性，然后利用单调队列的特征去实现

备注 §

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

题目1.和至少为 K 的最短子数组 §

题目描述 §

给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。

子数组 是数组中 连续 的一部分。

提示：

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

测试链接 §

862.和至少为 K 的最短子数组

思路 §

本题用到 构建前缀和 的技巧

答案 §

const (
	MAXN    = 1e5 + 1
	MAX_INT = math.MaxInt
)
 
var (
	// sum[0]: 前 0 个数的前缀和
	// sum[i]: 前 i 个数的前缀和
	sum        = [MAXN]int{}
	deque      = [MAXN]int{}
	head, tail = 0, 0
)
 
func shortestSubarray(nums []int, k int) int {
	head, tail = 0, 0
	n := len(nums)
	// 构造前缀和
	for i, num := range nums {
		sum[i+1] = sum[i] + num
	}
	ans := MAX_INT
	for i := 0; i <= n; i++ {
		// 单调队列有值，并且当前前缀和 - 队列头前缀和，达标
		for head < tail && sum[i]-sum[deque[head]] >= k {
			ans = min(ans, i-deque[head])
			// head 从队头弹出，已经收集了答案，之后不再参与答案了
			// 因为即使后面还有元素能以这个头元素为子数组左侧，达标
			// 但是长度更长了，不可能是最佳答案
			head++
		}
		// 队头 -> 队尾: 小 -> 大
		// 单调队列有值，并且当前前缀和 > 队列尾前缀和
		for head < tail && sum[deque[tail-1]] >= sum[i] {
			// 当前队尾元素 deque[tail-1] 记为 tail：大
			// 当前将要入队元素 i 记为 i：小
			// 将来后面还有元素能以 tail 为子数组左侧达标记为 future
			// 若：future - tail（大） >= k 成立，子数组长
			// 则：future - i（小） >= k 必定成立，子数组短
			// 所以 tail 不会再参与答案了，因为参与了也不可能是最佳答案
			// 将 tail 弹出队尾
			tail--
		}
		deque[tail] = i
		tail++
	}
	if ans == MAX_INT {
		return -1
	}
	return ans
}

题目2.满足不等式的最大值 §

题目描述 §

给你一个数组 points 和一个整数 k 。数组中每个元素都表示二维平面上的点的坐标，并按照横坐标 x 的值从小到大排序。也就是说 points[i] = [xi, yi] ，并且在 1 <= i < j <= points.length 的前提下， xi < xj 总成立。

请你找出 yi + yj + |xi - xj| 的 最大值，其中 |xi - xj| <= k 且 1 <= i < j <= points.length。

题目测试数据保证至少存在一对能够满足 |xi - xj| <= k 的点。

测试链接 §

1499.满足不等式的最大值

思路 §

因为 points 按 x 升序，所以 yi + yj + |xi - xj| = yi + yj + xj - xi = i[y-x] + j[y+x]

答案 §

const (
	MAXN    = 1e5 + 1
	MIN_INT = math.MinInt
)
 
var (
	deque      = [MAXN][2]int{} // [x, y]
	head, tail = 0, 0
)
 
func findMaxValueOfEquation(points [][]int, k int) int {
	head, tail = 0, 0
	n := len(points)
	ans := MIN_INT
	for i := 0; i < n; i++ {
		x := points[i][0]
		y := points[i][1]
		for head < tail && x-deque[head][0] > k {
			// 单调队列头部点的 x 与当前点 x 的距离超过了 k
			// 单调队列头部点不满足题意了（过期了），从头部弹出
			head++
		}
		if head < tail {
			ans = max(ans, deque[head][1]-deque[head][0]+y+x)
		}
		// 队头 -> 队尾: 大 -> 小 (y-x)
		for head < tail && deque[tail-1][1]-deque[tail-1][0] <= y-x {
			tail--
		}
		deque[tail][0] = x
		deque[tail][1] = y
		tail++
	}
	return ans
}

题目3.你可以安排的最多任务数目 §

题目描述 §

给你 n 个任务和 m 个工人。每个任务需要一定的力量值才能完成，需要的力量值保存在下标从 0 开始的整数数组 tasks 中，第 i 个任务需要 tasks[i] 的力量才能完成。每个工人的力量值保存在下标从 0 开始的整数数组 workers 中，第 j 个工人的力量值为 workers[j] 。每个工人只能完成 一个 任务，且力量值需要 大于等于 该任务的力量要求值（即 workers[j] >= tasks[i] ）。

除此以外，你还有 pills 个神奇药丸，可以给 一个工人的力量值 增加 strength 。你可以决定给哪些工人使用药丸，但每个工人 最多 只能使用 一片 药丸。

给你下标从 0 开始的整数数组 tasks 和 workers 以及两个整数 pills 和 strength ，请你返回 最多 有多少个任务可以被完成。

提示：

• n == tasks.length
• m == workers.length
• 1 <= n, m <= 5 * 10^4
• 0 <= pills <= m
• 0 <= tasks[i], workers[j], strength <= 10^9

测试链接 §

2071.你可以安排的最多任务数目

思路 §

本题大思路用到 二分答案法

单调性：两个数组排序

答案 §

const (
	MAXN = 5e4 + 1
)
 
var (
	theTasks    []int
	theWorkers  []int
	thePills    int
	theStrength int
	deque       = [MAXN]int{}
	head, tail  = 0, 0
)
 
func maxTaskAssign(tasks []int, workers []int, pills int, strength int) int {
	sort.Ints(tasks)
	sort.Ints(workers)
	theTasks = tasks
	theWorkers = workers
	thePills = pills
	theStrength = strength
	n := len(tasks)
	m := len(workers)
	l := 0         // 最少做 0 个任务
	r := min(n, m) // 最多做任务数和工人数较小值个任务
	mid := 0
	ans := 0
	for l <= r { // 二分答案法
		mid = l + (r-l)>>1
		if f(0, mid, m-mid, m) {
			ans = mid
			l = mid + 1
		} else {
			r = mid - 1
		}
	}
	return ans
}
 
// tasks[tl:tr]: 需要力量最小的几个任务
// workers[wl:wr]: 力量值最大的几个工人
// 在药的数量不超情况下，能不能每个工人都做一个任务
func f(tl, tr, wl, wr int) bool {
	head, tail = 0, 0
	// 已经使用的药的数量
	cnt := 0
	// i: 工人编号
	// j: 任务编号
	for i, j := wl, tl; i < wr; i++ {
		for ; j < tr && theTasks[j] <= theWorkers[i]; j++ {
			// 工人不吃药的情况下，去解锁任务
			deque[tail] = j
			tail++
		}
		if head < tail && theTasks[deque[head]] <= theWorkers[i] {
			// i 号工人做了 deque[head] 号任务（力量最小的工人做最简单的任务）
			head++
		} else {
			// 吃药之后的逻辑
			for ; j < tr && theTasks[j] <= theWorkers[i]+theStrength; j++ {
				// 工人吃药的情况下，去解锁任务
				deque[tail] = j
				tail++
			}
			// 吃药的情况下可以完成任务，并且有药可以吃
			if head < tail && cnt+1 <= thePills {
				cnt++
				// 贪心：吃了药了，要做能做到的最难的任务
				tail--
			} else {
				return false
			}
		}
	}
	return true
}

复杂度 §

• 时间复杂度：$O(n\ast lo{g}^n)+O(m\ast lo{g}^m)+O(min(n,m)\ast lo{g}^{min(n,m)})$，两个数组排序 + 二分答案法
• 空间复杂度：$O(n)$，双端队列空间