【算法】-单调队列
目录
什么是单调队列
区域内最大值
区域内最小值
什么是单调队列
说到单调队列，其实就是一个双端队列， 顾名思义，单调队列的重点分为「单调」和「队列」。「单调」指的是元素的「规律」——递增（或递减）。「队列」指的是元素只能从队头和队尾进行操作。
其内部元素在队列内维持单调特性(递增或递减)，类似单调栈，但是与单调栈FILO不同的是队列的FIFO的特性，配合滑动窗口的思想，可以解决区间内最值的问题。
区域内最大值
例题：239. 滑动窗口最大值 - 力扣（LeetCode）
我们来简单分析一下，题目要求的是滑动窗口内最大值，也就是区间内的最大值。这时候如果我们用暴力解法，维护一个双指针的滑窗和窗口内最大值，当窗口右移时，我们要比较新加入元素与窗口内最大值，选择是否更新。
如果是更新最大值的情况还好办，但是我们设想一下不理想的情况，新加入的元素不比窗口最大值大，同时移出窗口的元素恰恰是窗口最大值！那么这样一来，区间内的最大值是什么呢？这是没办法直接得出的，在这里还要遍历整个窗口重新寻找窗口最大值，太浪费时间了。
这时候用单调队列就能很好的解决问题，因为队列元素的单调性，使得获取最值和维护更新最值的操作自然一体。单调队列在入队时，比较来判断加入后会不会破坏单调性，不会则加入，会就出队原来的元素直到加入后满足单调性，这一行为可以抽象为滑动窗口滑的过程，同时还有注意根据题意在窗口大小k范围更新记录答案。
总的来说，单调队列就是以下3个步骤：
- 入（元素进入队尾，同时维护队列单调性）
- 出（元素离开队首）
- 记录/维护答案（根据队首）
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 && nums[q[len(q)-1]] <= x {
q = q[:len(q)-1] // 维护 q 的单调性
}
q = append(q, i) // 入队
// 2. 出
if i-q[0] >= k { // 队首已经离开窗口了
q = q[1:] // Go 的切片是 O(1) 的
}
// 3. 记录答案
if i >= k-1 {
// 由于队首到队尾单调递减，所以窗口最大值就是队首
ans = append(ans, nums[q[0]])
}
}
return ans
}区域内最小值
例题：2398. 预算内的最多机器人数目 - 力扣（LeetCode）
题目要求机器人连续运行，看成一个连续子数组，题目要求计算最长子数组长度。枚举子数组右端点 right，我们需要知道此时左端点 left 的最小值，这样子数组尽量长。
由于有 budget 的限制，所以 right 越大，left 也越大，有单调性，可以用滑动窗口解决。套路如下：
- 入：chargeTimes[right] 进入窗口时，弹出队尾的 ≤chargeTimes[right] 的元素。
- 出：如果总开销超过 budget，则不断移出左端点，直到总开销不超过 budget。特别地，如果左端点恰好等于队首，则弹出队首。
- 更新答案：用窗口长度 right−left+1 更新答案的最大值。
注意：为了方便判断队首是否要出队，单调队列中保存的是下标。
func maximumRobots(chargeTimes, runningCosts []int, budget int64) (ans int) {
q := []int{}
sum := int64(0)
left := 0
for right, t := range chargeTimes {
// 1. 入
for len(q) > 0 && t >= chargeTimes[q[len(q)-1]] {
q = q[:len(q)-1]
}
q = append(q, right)
sum += int64(runningCosts[right])
// 2. 出
for len(q) > 0 && int64(chargeTimes[q[0]])+int64(right-left+1)*sum > budget {
if q[0] == left {
q = q[1:]
}
sum -= int64(runningCosts[left])
left++
}
// 3. 更新答案
ans = max(ans, right-left+1)
}
return
}