单调队列一般能快速求出一段区间里的最大值。
保持队列单调:当数字 >= / <= 队尾元素时,及时替换队尾元素
保持窗口大小:当窗口超出范围时,及时弹出队头元素
var maxSlidingWindow = function(nums, k) {
const queue = []
const n = nums.length
const res = []
for(let i = 0; i < n; i++){
if(queue.length && i - queue[0] + 1 > k){
queue.shift()
}
while(queue.length && nums[queue[queue.length - 1]] <= nums[i]){
queue.pop()
}
queue.push(i)
if(i >= k - 1) res.push(nums[queue[0]])
}
return res
};
var longestSubarray = function(nums, limit) {
const n = nums.length
const minQueue = []
const maxQueue = []
let res = 0
for(let i = 0, j = 0; i < n; i++){
// 维护minQueue,由于是求最长连续子数组的长度,所以剔除队尾的条件是 > 或 <,不需要=
while(minQueue.length && minQueue[minQueue.length - 1] > nums[i]){
minQueue.pop()
}
minQueue.push(nums[i])
// 维护maxQueue
while(maxQueue.length && maxQueue[maxQueue.length - 1] < nums[i]){
maxQueue.pop()
}
maxQueue.push(nums[i])
// 如果此时不满足题意,开始移动左端点j
if(minQueue.length && maxQueue.length && maxQueue[0] - minQueue[0] > limit){
if(nums[j] === minQueue[0]){
minQueue.shift()
}
if(nums[j] === maxQueue[0]){
maxQueue.shift()
}
j++
}
res = Math.max(res, i - j + 1)
}
return res
};
var maximumRobots = function(chargeTimes, runningCosts, budget) {
const n = chargeTimes.length
const maxQueue = []
let res = 0
for(let i = 0, j = 0, sum = 0; i < n; i++){
// 维护单调队列
while(maxQueue.length && chargeTimes[i] >= chargeTimes[maxQueue[maxQueue.length - 1]]){
maxQueue.pop()
}
maxQueue.push(i)
// 计算窗口合法性
sum += runningCosts[i]
while(maxQueue.length && chargeTimes[maxQueue[0]] + (i - j + 1) * sum > budget){
if(maxQueue[0] === j) maxQueue.shift()
sum -= runningCosts[j]
j += 1
}
res = Math.max(res, i - j + 1)
}
return res
};
var shortestSubarray = function(nums, k) {
const n = nums.length
const s = new Array(n + 1).fill(0)
for(let i = 0; i < n; i++){
s[i + 1] = s[i] + nums[i]
}
// 注意这道题里面nums的数有可能是负数,如果是正数则可以用双指针滑窗解决
// 所以针对左端点j,我们需要使用单调队列维护可能是 sum >= k的最短子数组的j。
let res = Infinity
const queue = []
for(let i = 0; i <= n; i++){
// 维护队列
while(queue.length && s[queue[queue.length - 1]] >= s[i]){
queue.pop()
}
queue.push(i)
// 检验当前窗口, s[i]是前缀和
while(queue.length && s[i] - s[queue[0]] >= k){
// 如果当前子数组sum符合 >= k
res = Math.min(res, i - queue[0])
queue.shift()
}
}
return res === Infinity ? -1 : res
};
var findMaxValueOfEquation = function(points, k) {
// 思路:要求满足 |xi - xj| <= k 情况下的 |xi - xj| + yi + yj 的最大值
// 由于当i < j时,xi < xj,所以转化为求-xi + xj + yi + yj => (yi - xi) + (xj + yj)的最大值,其中xj - xi <= k
// 转化为:求窗口size <= k时的 yi - xi 的最大值
const n = points.length
const queue = []
let res = -Infinity
for(let i = 0; i < n; i++){
const [x, y] = points[i]
// 不满足窗口了,剔除队头
while(queue.length && x - queue[0][0] > k){
queue.shift()
}
if(queue.length){
res = Math.max(res, x + y + queue[0][1])
}
// 遇到比队尾大的,则剔除队尾,将新的y-x插入
while(queue.length && queue[queue.length - 1][1] <= y - x){
queue.pop()
}
queue.push([x, y - x])
}
return res
};