1 篇博文 含有标签「longestSubarray」

nums = [8, 2, 4, 7]
limit = 4

/**
 * @param {number[]} nums
 * @param {number} limit
 * @return {number}
 */
var longestSubarray = function (nums, limit) {
  /**
    整理题目：
    数组 nums，连续元素间的绝对值 <= limit，要求返回符合的窗口长度（max）
    👉 绝对值考虑区间的最大最小值
    👉 两个队列来分别记录区间拥有的最大、最小值
    👉 没有长度限制，因此更新绝对值没有限定条件，每次移动右指针都需要更新
    关注：何时收缩左指针 👉 一旦绝对值 > limit 就需要收缩左指针
    收缩左指针注意事项：
    判断左指针对应元素是否在两个队列的队头，如果在，将队列头部出队（单调队列只关注队头，nums[l] 出现在队中或者队尾，一旦有新的更符合条件的元素入队，随时会被出队，因此不关注）

    1. 遍历整个 nums，循环结束条件是 r < nums.length
    2. 判断极值队列中不为空，将队列尾部大于/小于 nums[r] 的元素移除出队
    2. 分别将 nums[r] 压入队列
    3. while 循环设置收缩左指针的逻辑 Math.abs(max-min) > k 时，收缩左指针 l+【收缩之前查看即将被排除的 nums[l] 是否在极值队列的队头影响结果，如果在，将队列队头元素出队】 
    */
  let l = 0
  let r = 0
  let queueMax = []
  let queueMin = []

  let res = 0
  while (r < nums.length) {
    while (queueMax.length && nums[r] > queueMax[queueMax.length - 1]) {
      queueMax.pop()
    }
    queueMax.push(nums[r])

    while (queueMin.length && nums[r] < queueMin[queueMin.length - 1]) {
      queueMin.pop()
    }

    queueMin.push(nums[r])

    // l 收缩逻辑
    if (queueMax.length && queueMin.length && Math.abs(queueMax[0] - queueMin[0]) > limit) {
      // 收缩之前检查(检查一次就行，不需要用 while)
      if (queueMax[0] == nums[l]) {
        queueMax.shift()
      }
      if (queueMin[0] == nums[l]) {
        queueMin.shift()
      }

      // 收缩区间
      l++
    }

    res = Math.max(r - l + 1, res)
    r++
  }
  console.log({ res })
  return res
}