综述
模板
例题
- 剑指 Offer 59 - I. 滑动窗口的最大值">【窗口内单调栈】剑指 Offer 59 - I. 滑动窗口的最大值
- 滑动窗口最大值">【单调队列】滑动窗口最大值
- 42. 接雨水">【单调栈/困难】42. 接雨水
- 480. 滑动窗口中位数">【有序数组】480. 滑动窗口中位数
- 220. 存在重复元素 III">【距离对/中】220. 存在重复元素 III
- 683. K 个关闭的灯泡">【山峰问题/困难】683. K 个关闭的灯泡
- 1438. 绝对差不超过限制的最长连续子数组">【大堆小堆/中】1438. 绝对差不超过限制的最长连续子数组

综述

单调性的维持一般采用单调队列、单调栈、堆、优先队列等保持窗口内状态数据的单调性。

模板

例题

【窗口内单调栈】剑指 Offer 59 - I. 滑动窗口的最大值

难度困难308收藏分享切换为英文接收动态反馈
给定一个数组 nums 和滑动窗口的大小 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

提示：
你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。
注意：本题与主站 239 题相同：https://leetcode-cn.com/problems/sliding-window-maximum/

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
  let st = [], ans=[];
  for (let i = 0; i < nums.length; i++) {
    // 单调递减栈，维持第一个数字最大
    while (st.length && nums[st[st.length - 1]] < nums[i]) {
      st.pop();
    }
    st.push(i);
    // 栈中的元素的位置已经不在窗口范围内，弹出栈底元素。
    while (st.length && st[0] <= i-k) {
      st.shift();
    }
    if (i >= k-1) {
      // 更新数据，移动窗口左指针。
      ans.push(nums[st[0]]);
    }
  }
  return ans;
};

【单调队列】滑动窗口最大值

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

返回滑动窗口中的最大值。

示例 1：

输入：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
示例 2：

输入：nums = [1], k = 1
输出：[1]
示例 3：

输入：nums = [1,-1], k = 1
输出：[1,-1]
示例 4：

输入：nums = [9,11], k = 2
输出：[11]
示例 5：

输入：nums = [4,-2], k = 2
输出：[4]

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
  const q = new MQueue();
  for (let i = 0; i < k; i++) {
    q.push(nums[i]);
  }
  let ans = [q.first()];
  for (let i = k; i < nums.length; i++) {
    q.pop(nums[i-k]);
    q.push(nums[i]);
    ans.push(q.first());
  }
  return ans;
};

class MQueue {
  constructor(){
    this.data = [];
    this.comp = (a, b) => a < b;
  }
  push(d) {
    while (this.data.length && this.comp(this.data[this.data.length - 1], d)) {
      this.data.pop();
    }
    this.data.push(d);
  }
  pop(d) {
    if (this.data.length && d === this.data[0]) {
      this.data.shift();
    }
  }
  first() {
    return this.data[0];
  }
}

【单调栈/困难】42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5] 输出：9

提示：

n == height.length
0 <= n <= 3 * 104
0 <= height[i] <= 105 ```javascript // 解法一：单调栈，直接找木桶的两个边界，右边比左边大，左边比右边大的，再while循环后，一次性再计算，while循环中不计算中间状态。 /**
- @param {number[]} height
- @return {number} */ var trap = function(height) { const mq = []; const compute = (l, r) => { // 以左右边界为墙，一次扫描计算内围雨水量。 let up = Math.min(height[l], height[r]); if (up === 0) return 0; let s = 0, i = l + 1; while (i < r) { s += (up - height[i++]); } return s; };
let r = 0, ans = 0; while (r < height.length) { while(mq.length && height[mq[mq.length - 1]] < height[r]) {
```
let pre = mq.pop();
if (mq.length === 0) {
  // 找到右侧大的边界了，这是栈被弹空，直接计算两个边界间的雨水量。
  ans += compute(pre, r);
}
```
} mq.push(r); r++; } // 栈中还有数据，符合单调递减，两两计算。 for (let i = 0; i < mq.length-1; i++) { ans += compute(mq[i], mq[i+1]); } return ans; };

// 解法二：每次计算新元素与栈顶产生的雨水量。 /**

@param {number[]} height
@return {number} */ var trap = function(height) { const mq = []; let r = 0, ans = 0; while (r < height.length) { while(mq.length && height[mq[mq.length - 1]] < height[r]) { let pre = mq.pop(); if (mq.length === 0) {
```
 break;
```
} // 左侧为：mq[mq.length - 1]，右侧为r // 距离为：两边的木桶不计算水，所以长度为r - mq[mq.length - 1] + 1 - 2 = r - mq[mq.length - 1] - 1 ans += (r - mq[mq.length - 1] - 1) * (Math.min(height[r], height[mq[mq.length - 1]]) - height[pre]); } mq.push(r); r++; } return ans; };

// 解法三：双向单调栈 /**

@param {number[]} height
@return {number} */ var trap = function(height) { let r = 0, ans = 0; const compute = (ll, rr) => { const base = Math.min(height[ll], height[rr]); let i = ll + 1, s = 0; while (i < rr) { s += (base - height[i++]); } return s; };

// 从左向右计算，去掉栈空间，只保留一个max指针 let leftMax = 0; while (r < height.length) { // 这个方向也计算边界相等的情况，从右向左的时候就只需要计算小于等于的状态即可。 if (height[r] >= height[leftMax]) { ans += compute(leftMax, r); leftMax = r; } r++; }

// 从右向左计算，去掉栈空间，只保留一个max指针 let l = height.length - 1, rightMax = height.length - 1; while (l >= 0) { if (height[l] > height[rightMax]) { ans += compute(l, rightMax); rightMax = l; } l—; } return ans; }; ```

【有序数组】480. 滑动窗口中位数
难度困难307收藏分享切换为英文接收动态反馈
中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。
例如：

[2,3,4]，中位数是 3
[2,3]，中位数是 (2 + 3) / 2 = 2.5

给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。

示例：
给出 nums = [1,3,-1,-3,5,3,6,7]，以及 k = 3。

窗口位置中位数
———————- ——-
[1 3 -1] -3 5 3 6 7 1
1 [3 -1 -3] 5 3 6 7 -1
1 3 [-1 -3 5] 3 6 7 -1
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] 6

因此，返回该滑动窗口的中位数数组 [1,-1,-1,3,5,6]。

提示：

你可以假设 k 始终有效，即：k 始终小于等于输入的非空数组的元素个数。

与真实值误差在 10 ^ -5 以内的答案将被视作正确答案。

/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var medianSlidingWindow = function (nums, k) {
const temp = [];
for (let i = 0; i < k; i++) {
  temp.push(nums[i]);
}
temp.sort((a, b) => a - b);
const getM = (temp) => {
  if (temp.length % 2 === 0) {
    return (temp[temp.length >>> 1] + temp[ -1 + (temp.length >>> 1)])/2;
  }
  return temp[temp.length >>> 1];
};

const replace = (temp, first, second) => {
  let l = 0, r = temp.length;
  let m = Number.MAX_SAFE_INTEGER;
  while (l < r) {
    m = l + ((r - l) >>> 1);
    if (temp[m] === first) {
      break;
    } else if (temp[m] > first) {
      r = m;
    } else if (temp[m] < first) {
      l = m + 1;
    }
  }
  temp[m] = second;
  while (m - 1 >= 0 && temp[m] < temp[m-1]) {
    [temp[m], temp[m-1]] = [temp[m-1], temp[m]];
    m--;
  }
  while (m + 1 < temp.length && temp[m] > temp[m+1]) {
    [temp[m], temp[m+1]] = [temp[m+1], temp[m]];
    m++;
  }
};

ans = [getM(temp)];
for (let i = k; i < nums.length; i++) {
  replace(temp, nums[i-k], nums[i]);
  ans.push(getM(temp));
}
return ans;
};

【距离对/中】220. 存在重复元素 III

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
如果存在则返回 true，不存在返回 false。

示例 1：
输入：nums = [1,2,3,1], k = 3, t = 0 输出：true
示例 2：
输入：nums = [1,0,1,1], k = 1, t = 2 输出：true
示例 3：
输入：nums = [1,5,9,1,5,9], k = 2, t = 3 输出：false

提示：

0 <= nums.length <= 2 * 104
-231 <= nums[i] <= 231 - 1
0 <= k <= 104

0 <= t <= 231 - 1

/**
* @param {number[]} nums
* @param {number} k
* @param {number} t
* @return {boolean}
*/
var containsNearbyAlmostDuplicate = function(nums, k, t) {
let l = 0, r = 0, temp = [];
for (let i = 0; i < k + 1; i++) {
  temp.push(nums[i]);
}
temp.sort((a, b) => a - b);
const find = (temp, t) => {
  // 双指针查找距离对小于等于t的存在。
  let j = 0;
  for (let i = 1; i < temp.length; i++) {
    if (Math.abs(temp[j] - temp[i]) <= t) {
      return true;
    } else {
      j++;
    }
  }
  return false;
};

// 滑动窗口替换元素，利用冒泡保持有序性。
const replace = (temp, first, second) => {
  let l = 0, r = temp.length;
  let m = Number.MAX_SAFE_INTEGER;
  while (l < r) {
    m = l + ((r - l) >>> 1);
    if (temp[m] === first) {
      break;
    } else if (temp[m] > first) {
      r = m;
    } else if (temp[m] < first) {
      l = m + 1;
    }
  }
  temp[m] = second;
  while (m - 1 >= 0 && temp[m] < temp[m-1]) {
    [temp[m], temp[m-1]] = [temp[m-1], temp[m]];
    m--;
  }
  while (m + 1 < temp.length && temp[m] > temp[m+1]) {
    [temp[m], temp[m+1]] = [temp[m+1], temp[m]];
    m++;
  }
};

if (find(temp, t)) {
  return true;
}
for (let i = k + 1; i < nums.length; i++) {
  replace(temp, nums[i- k - 1], nums[i]);
  if (find(temp, t)) {
    return true;
  }
}
return false;
};

【山峰问题/困难】683. K 个关闭的灯泡

难度困难55收藏分享切换为英文接收动态反馈
N 个灯泡排成一行，编号从 1 到 N 。最初，所有灯泡都关闭。每天只打开一个灯泡，直到 N 天后所有灯泡都打开。
给你一个长度为 N 的灯泡数组 blubs ，其中 bulls[i] = x 意味着在第 (i+1) 天，我们会把在位置 x 的灯泡打开，其中 i 从 0 开始，x 从 1 开始。
给你一个整数 K ，请你输出在第几天恰好有两个打开的灯泡，使得它们中间正好有 K 个灯泡且这些灯泡全部是关闭的。
如果不存在这种情况，返回 -1 。如果有多天都出现这种情况，请返回最小的天数。

示例 1：
输入： bulbs: [1,3,2] K: 1 输出：2 解释：第一天 bulbs[0] = 1，打开第一个灯泡 [1,0,0] 第二天 bulbs[1] = 3，打开第三个灯泡 [1,0,1] 第三天 bulbs[2] = 2，打开第二个灯泡 [1,1,1] 返回2，因为在第二天，两个打开的灯泡之间恰好有一个关闭的灯泡。
示例 2：
输入： bulbs: [1,2,3] k: 1 输出：-1

提示：

1 <= N <= 20000
1 <= bulbs[i] <= N
bulbs 是一个由从 1 到 N 的数字构成的排列

0 <= K <= 20000

/**
* @param {number[]} bulbs
* @param {number} k
* @return {number}
*/
var kEmptySlots = function(bulbs, k) {
const t = new Array(bulbs.length).fill(0);
let r = 0;
// bulbs[i] = j 表示的是第（i+1）天，第j个位置开灯， 数组中存入的是等的序号。
// t[i] = j 记录第i个位置在第j天开灯，数组中存的是的天的序号，维度进行了转化
// 将原来的求解开个灯泡问题 转为为开启每个灯的开启时间点的窗口问题。
while (r < bulbs.length) {
  t[bulbs[r]-1] = r;
  r++;
}
let ans = Number.MAX_SAFE_INTEGER;
r = k + 1; // 固定窗口大小，只保留右指针，左指针可以直接计算得到。
while (r < t.length) {
  let max = Math.max(t[r - k - 1], t[r]);
  let slide = false;
  for (let i = r - k; i < r; i++) {
    if (t[i] < max) {
      // 找到一个比两端的大值还小的点，说明这个区间无效
      // 右指针直接向右移动i个位置
      r = i + k + 1;
      slide = true;
      break;
    }
  }
  if (slide) continue;
  // 找到一个解，由于解是最小的按个天数的大小为：左右两天的大值的下一天。
  // min求全局最小值。
  ans = Math.min(ans, max + 1);
  r += k + 1;
}
return ans === Number.MAX_SAFE_INTEGER ? -1 : ans;
};

【大堆小堆/中】1438. 绝对差不超过限制的最长连续子数组

难度中等206收藏分享切换为英文接收动态反馈
给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。
如果不存在满足条件的子数组，则返回 0 。

示例 1：

输入：nums = [8,2,4,7], limit = 4
输出：2
解释：所有子数组如下：
[8] 最大绝对差 |8-8| = 0 <= 4.
[8,2] 最大绝对差 |8-2| = 6 > 4.
[8,2,4] 最大绝对差 |8-2| = 6 > 4.
[8,2,4,7] 最大绝对差 |8-2| = 6 > 4.
[2] 最大绝对差 |2-2| = 0 <= 4.
[2,4] 最大绝对差 |2-4| = 2 <= 4.
[2,4,7] 最大绝对差 |2-7| = 5 > 4.
[4] 最大绝对差 |4-4| = 0 <= 4.
[4,7] 最大绝对差 |4-7| = 3 <= 4.
[7] 最大绝对差 |7-7| = 0 <= 4.
因此，满足题意的最长子数组的长度为 2 。

示例 2：
输入：nums = [10,1,2,4,7,2], limit = 5
输出：4
解释：满足题意的最长子数组是 [2,4,7,2]，其最大绝对差 |2-7| = 5 <= 5 。

示例 3：
输入：nums = [4,2,2,2,4,4,2,2], limit = 0
输出：3

提示：

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
0 <= limit <= 10^9 ```javascript /**
- @param {number[]} nums
- @param {number} limit
- @return {number} */ var longestSubarray = function(nums, limit) { let ans = 0, l = 0, r = 0, min = new AscQueue(), max = new DescQueue(); while (r < nums.length) { min.push(nums[r]); max.push(nums[r]); while (!min.isEmpty() && !max.isEmpty() && max.front() - min.front() > limit) { if (nums[l] === min.front()) {
```
min.popFront();
```
  } if (nums[l] === max.front()) {
```
max.popFront();
```
  } l++; } ans = Math.max(ans, r - l + 1); r++; } return ans; };

class MQueue { constructor(){ this.data = []; this.start = -1; } push(d) { while (!this.isEmpty() && this.compare(this.last(), d)) { this.data.pop(); }

this.data.push(d);
if (this.start === -1) {
  this.start++;
}

}

popFront() { this.start++; }

front() { return this.data[this.start]; }

last() { return this.data[this.data.length - 1]; }

isEmpty() { return (this.start === -1) || this.data.length === this.start; } }

class AscQueue extends MQueue { compare(a, b) { return a > b; } } class DescQueue extends MQueue { compare(a, b) { return a < b; } } ```

单调性

综述

模板