1438.绝对差不超过限制的最长连续子数组

链接：1438.绝对差不超过限制的最长连续子数组
难度：Medium
标签：队列、数组、有序集合、滑动窗口、单调队列、堆（优先队列）
简介：给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。

题解 1 - typescript

• 编辑时间：2021-02-21
• 执行用时：208ms
• 内存消耗：61.8MB
• 编程语言：typescript
• 解法介绍：滑动窗口,记录最值进行比较。

function longestSubarray(nums: number[], limit: number): number {
  const zero = nums[0];
  let l = 0;
  let r = 0;
  let max = zero;
  let min = zero;
  let win: Record<number, number> = { [zero]: 1 };
  let ans = 1;
  let sortArr = [zero];
  const len = nums.length;
  while (++r < len) {
    const num = nums[r];
    const value = win[num];
    win[num] = 1 + (value ?? 0);
    if (!value) {
      if (num > max) sortArr.push((max = num));
      else if (num < min) sortArr.unshift((min = num));
      else {
        for (let i = 0, l = sortArr.length; i < l; i++) {
          if (sortArr[i] > num) {
            sortArr.splice(i, 0, num);
            break;
          }
        }
      }
      while (l < r && max - min > limit) {
        const prevNum = nums[l++];
        const count = win[prevNum];
        win[prevNum] = count - 1;
        if (count === 1) {
          if (prevNum === max) max = sortArr[sortArr.length - 2];
          else if (prevNum === min) min = sortArr[1];
          for (let i = 0, l = sortArr.length; i < l; i++) {
            if (sortArr[i] === prevNum) {
              sortArr.splice(i, 1);
              break;
            }
          }
        }
      }
    }
    ans = Math.max(ans, r - l + 1);
  }
  return ans;
}

题解 2 - typescript

• 编辑时间：2021-07-21
• 执行用时：2712ms
• 内存消耗：65.9MB
• 编程语言：typescript
• 解法介绍：遍历每个长度，利用单调栈维护滑动窗口中的最值。

function longestSubarray(nums: number[], limit: number): number {
  const n = nums.length;
  return search();
  function search(l = 0, r = nums.length): number {
    if (l === r) return l;
    const mid = (l + r + 1) >> 1;
    if (check(mid)) l = mid;
    else r = mid - 1;
    return search(l, r);
  }
  function check(len: number): boolean {
    const qMax: number[] = [];
    const qMin: number[] = [];
    for (let i = 0; i < n; i++) {
      const num = nums[i];
      while (qMax.length && nums[qMax[qMax.length - 1]] < num) qMax.pop();
      while (qMin.length && nums[qMin[qMin.length - 1]] > num) qMin.pop();
      qMax.push(i);
      qMin.push(i);
      if (i + 1 < len) continue;
      if (i - qMax[0] === len) qMax.shift();
      if (i - qMin[0] === len) qMin.shift();
      if (nums[qMax[0]] - nums[qMin[0]] <= limit) return true;
    }
    return false;
  }
}