Question

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

English Version

题目描述

给你一个整数数组 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

解法

方法一：有序集合 + 滑动窗口

我们可以枚举每个位置作为子数组的右端点，找到其对应的最靠左的左端点，满足区间内中最大值与最小值的差值不超过 $limit$。过程中，我们用有序集合维护窗口内的最大值和最小值。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 是数组 nums 的长度。

from sortedcontainers import SortedList


class Solution:
  def longestSubarray(self, nums: List[int], limit: int) -> int:
    sl = SortedList()
    ans = j = 0
    for i, v in enumerate(nums):
      sl.add(v)
      while sl[-1] - sl[0] > limit:
        sl.remove(nums[j])
        j += 1
      ans = max(ans, i - j + 1)
    return ans

class Solution {
  public int longestSubarray(int[] nums, int limit) {
    TreeMap<Integer, Integer> tm = new TreeMap<>();
    int ans = 0, j = 0;
    for (int i = 0; i < nums.length; ++i) {
      tm.put(nums[i], tm.getOrDefault(nums[i], 0) + 1);
      while (tm.lastKey() - tm.firstKey() > limit) {
        tm.put(nums[j], tm.get(nums[j]) - 1);
        if (tm.get(nums[j]) == 0) {
          tm.remove(nums[j]);
        }
        ++j;
      }
      ans = Math.max(ans, i - j + 1);
    }
    return ans;
  }
}

class Solution {
public:
  int longestSubarray(vector<int>& nums, int limit) {
    multiset<int> s;
    int ans = 0, j = 0;
    for (int i = 0; i < nums.size(); ++i) {
      s.insert(nums[i]);
      while (*s.rbegin() - *s.begin() > limit) {
        s.erase(s.find(nums[j++]));
      }
      ans = max(ans, i - j + 1);
    }
    return ans;
  }
};

func longestSubarray(nums []int, limit int) (ans int) {
  tm := treemap.NewWithIntComparator()
  j := 0
  for i, v := range nums {
    if x, ok := tm.Get(v); ok {
      tm.Put(v, x.(int)+1)
    } else {
      tm.Put(v, 1)
    }
    for {
      a, _ := tm.Min()
      b, _ := tm.Max()
      if b.(int)-a.(int) > limit {
        if x, _ := tm.Get(nums[j]); x.(int) == 1 {
          tm.Remove(nums[j])
        } else {
          tm.Put(nums[j], x.(int)-1)
        }
        j++
      } else {
        break
      }
    }
    ans = max(ans, i-j+1)
  }
  return
}

function longestSubarray(nums: number[], limit: number): number {
  const ts = new TreapMultiSet<number>();
  let ans = 0;
  let j = 0;
  for (let i = 0; i < nums.length; ++i) {
    ts.add(nums[i]);
    while (ts.last() - ts.first() > limit) {
      ts.delete(nums[j++]);
    }
    ans = Math.max(ans, i - j + 1);
  }
  return ans;
}

type CompareFunction<T, R extends 'number' | 'boolean'> = (
  a: T,
  b: T,
) => R extends 'number' ? number : boolean;

interface ITreapMultiSet<T> extends Iterable<T> {
  add: (...value: T[]) => this;
  has: (value: T) => boolean;
  delete: (value: T) => void;

  bisectLeft: (value: T) => number;
  bisectRight: (value: T) => number;

  indexOf: (value: T) => number;
  lastIndexOf: (value: T) => number;

  at: (index: number) => T | undefined;
  first: () => T | undefined;
  last: () => T | undefined;

  lower: (value: T) => T | undefined;
  higher: (value: T) => T | undefined;
  floor: (value: T) => T | undefined;
  ceil: (value: T) => T | undefined;

  shift: () => T | undefined;
  pop: (index?: number) => T | undefined;

  count: (value: T) => number;

  keys: () => IterableIterator<T>;
  values: () => IterableIterator<T>;
  rvalues: () => IterableIterator<T>;
  entries: () => IterableIterator<[number, T]>;

  readonly size: number;
}

class TreapNode<T = number> {
  value: T;
  count: number;
  size: number;
  priority: number;
  left: TreapNode<T> | null;
  right: TreapNode<T> | null;

  constructor(value: T) {
    this.value = value;
    this.count = 1;
    this.size = 1;
    this.priority = Math.random();
    this.left = null;
    this.right = null;
  }

  static getSize(node: TreapNode<any> | null): number {
    return node?.size ?? 0;
  }

  static getFac(node: TreapNode<any> | null): number {
    return node?.priority ?? 0;
  }

  pushUp(): void {
    let tmp = this.count;
    tmp += TreapNode.getSize(this.left);
    tmp += TreapNode.getSize(this.right);
    this.size = tmp;
  }

  rotateRight(): TreapNode<T> {
    // eslint-disable-next-line @typescript-eslint/no-this-alias
    let node: TreapNode<T> = this;
    const left = node.left;
    node.left = left?.right ?? null;
    left && (left.right = node);
    left && (node = left);
    node.right?.pushUp();
    node.pushUp();
    return node;
  }

  rotateLeft(): TreapNode<T> {
    // eslint-disable-next-line @typescript-eslint/no-this-alias
    let node: TreapNode<T> = this;
    const right = node.right;
    node.right = right?.left ?? null;
    right && (right.left = node);
    right && (node = right);
    node.left?.pushUp();
    node.pushUp();
    return node;
  }
}

class TreapMultiSet<T = number> implements ITreapMultiSet<T> {
  private readonly root: TreapNode<T>;
  private readonly compareFn: CompareFunction<T, 'number'>;
  private readonly leftBound: T;
  private readonly rightBound: T;

  constructor(compareFn?: CompareFunction<T, 'number'>);
  constructor(compareFn: CompareFunction<T, 'number'>, leftBound: T, rightBound: T);
  constructor(
    compareFn: CompareFunction<T, any> = (a: any, b: any) => a - b,
    leftBound: any = -Infinity,
    rightBound: any = Infinity,
  ) {
    this.root = new TreapNode<T>(rightBound);
    this.root.priority = Infinity;
    this.root.left = new TreapNode<T>(leftBound);
    this.root.left.priority = -Infinity;
    this.root.pushUp();

    this.leftBound = leftBound;
    this.rightBound = rightBound;
    this.compareFn = compareFn;
  }

  get size(): number {
    return this.root.size - 2;
  }

  get height(): number {
    const getHeight = (node: TreapNode<T> | null): number => {
      if (node == null) return 0;
      return 1 + Math.max(getHeight(node.left), getHeight(node.right));
    };

    return getHeight(this.root);
  }

  /**
   *
   * @complexity `O(logn)`
   * @description Returns true if value is a member.
   */
  has(value: T): boolean {
    const compare = this.compareFn;
    const dfs = (node: TreapNode<T> | null, value: T): boolean => {
      if (node == null) return false;
      if (compare(node.value, value) === 0) return true;
      if (compare(node.value, value) < 0) return dfs(node.right, value);
      return dfs(node.left, value);
    };

    return dfs(this.root, value);
  }

  /**
   *
   * @complexity `O(logn)`
   * @description Add value to sorted set.
   */
  add(...values: T[]): this {
    const compare = this.compareFn;
    const dfs = (
      node: TreapNode<T> | null,
      value: T,
      parent: TreapNode<T>,
      direction: 'left' | 'right',
    ): void => {
      if (node == null) return;
      if (compare(node.value, value) === 0) {
        node.count++;
        node.pushUp();
      } else if (compare(node.value, value) > 0) {
        if (node.left) {
          dfs(node.left, value, node, 'left');
        } else {
          node.left = new TreapNode(value);
          node.pushUp();
        }

        if (TreapNode.getFac(node.left) > node.priority) {
          parent[direction] = node.rotateRight();
        }
      } else if (compare(node.value, value) < 0) {
        if (node.right) {
          dfs(node.right, value, node, 'right');
        } else {
          node.right = new TreapNode(value);
          node.pushUp();
        }

        if (TreapNode.getFac(node.right) > node.priority) {
          parent[direction] = node.rotateLeft();
        }
      }
      parent.pushUp();
    };

    values.forEach(value => dfs(this.root.left, value, this.root, 'left'));
    return this;
  }

  /**
   *
   * @complexity `O(logn)`
   * @description Remove value from sorted set if it is a member.
   * If value is not a member, do nothing.
   */
  delete(value: T): void {
    const compare = this.compareFn;
    const dfs = (
      node: TreapNode<T> | null,
      value: T,
      parent: TreapNode<T>,
      direction: 'left' | 'right',
    ): void => {
      if (node == null) return;

      if (compare(node.value, value) === 0) {
        if (node.count > 1) {
          node.count--;
          node?.pushUp();
        } else if (node.left == null && node.right == null) {
          parent[direction] = null;
        } else {
          // 旋到根节点
          if (
            node.right == null ||
            TreapNode.getFac(node.left) > TreapNode.getFac(node.right)
          ) {
            parent[direction] = node.rotateRight();
            dfs(parent[direction]?.right ?? null, value, parent[direction]!, 'right');
          } else {
            parent[direction] = node.rotateLeft();
            dfs(parent[direction]?.left ?? null, value, parent[direction]!, 'left');
          }
        }
      } else if (compare(node.value, value) > 0) {
        dfs(node.left, value, node, 'left');
      } else if (compare(node.value, value) < 0) {
        dfs(node.right, value, node, 'right');
      }

      parent?.pushUp();
    };

    dfs(this.root.left, value, this.root, 'left');
  }

  /**
   *
   * @complexity `O(logn)`
   * @description Returns an index to insert value in the sorted set.
   * If the value is already present, the insertion point will be before (to the left of) any existing values.
   */
  bisectLeft(value: T): number {
    const compare = this.compareFn;
    const dfs = (node: TreapNode<T> | null, value: T): number => {
      if (node == null) return 0;

      if (compare(node.value, value) === 0) {
        return TreapNode.getSize(node.left);
      } else if (compare(node.value, value) > 0) {
        return dfs(node.left, value);
      } else if (compare(node.value, value) < 0) {
        return dfs(node.right, value) + TreapNode.getSize(node.left) + node.count;
      }

      return 0;
    };

    return dfs(this.root, value) - 1;
  }

  /**
   *
   * @complexity `O(logn)`
   * @description Returns an index to insert value in the sorted set.
   * If the value is already present, the insertion point will be before (to the right of) any existing values.
   */
  bisectRight(value: T): number {
    const compare = this.compareFn;
    const dfs = (node: TreapNode<T> | null, value: T): number => {
      if (node == null) return 0;

      if (compare(node.value, value) === 0) {
        return TreapNode.getSize(node.left) + node.count;
      } else if (compare(node.value, value) > 0) {
        return dfs(node.left, value);
      } else if (compare(node.value, value) < 0) {
        return dfs(node.right, value) + TreapNode.getSize(node.left) + node.count;
      }

      return 0;
    };
    return dfs(this.root, value) - 1;
  }

  /**
   *
   * @complexity `O(logn)`
   * @description Returns the index of the first occurrence of a value in the set, or -1 if it is not present.
   */
  indexOf(value: T): number {
    const compare = this.compareFn;
    let isExist = false;

    const dfs = (node: TreapNode<T> | null, value: T): number => {
      if (node == null) return 0;

      if (compare(node.value, value) === 0) {
        isExist = true;
        return TreapNode.getSize(node.left);
      } else if (compare(node.value, value) > 0) {
        return dfs(node.left, value);
      } else if (compare(node.value, value) < 0) {
        return dfs(node.right, value) + TreapNode.getSize(node.left) + node.count;
      }

      return 0;
    };
    const res = dfs(this.root, value) - 1;
    return isExist ? res : -1;
  }

  /**
   *
   * @complexity `O(logn)`
   * @description Returns the index of the last occurrence of a value in the set, or -1 if it is not present.
   */
  lastIndexOf(value: T): number {
    const compare = this.compareFn;
    let isExist = false;

    const dfs = (node: TreapNode<T> | null, value: T): number => {
      if (node == null) return 0;

      if (compare(node.value, value) === 0) {
        isExist = true;
        return TreapNode.getSize(node.left) + node.count - 1;
      } else if (compare(node.value, value) > 0) {
        return dfs(node.left, value);
      } else if (compare(node.value, value) < 0) {
        return dfs(node.right, value) + TreapNode.getSize(node.left) + node.count;
      }

      return 0;
    };

    const res = dfs(this.root, value) - 1;
    return isExist ? res : -1;
  }

  /**
   *
   * @complexity `O(logn)`
   * @description Returns the item located at the specified index.
   * @param index The zero-based index of the desired code unit. A negative index will count back from the last item.
   */
  at(index: number): T | undefined {
    if (index < 0) index += this.size;
    if (index < 0 || index >= this.size) return undefined;

    const dfs = (node: TreapNode<T> | null, rank: number): T | undefined => {
      if (node == null) return undefined;

      if (TreapNode.getSize(node.left) >= rank) {
        return dfs(node.left, rank);
      } else if (TreapNode.getSize(node.left) + node.count >= rank) {
        return node.value;
      } else {
        return dfs(node.right, rank - TreapNode.getSize(node.left) - node.count);
      }
    };

    const res = dfs(this.root, index + 2);
    return ([this.leftBound, this.rightBound] as any[]).includes(res) ? undefined : res;
  }

  /**
   *
   * @complexity `O(logn)`
   * @description Find and return the element less than `val`, return `undefined` if no such element found.
   */
  lower(value: T): T | undefined {
    const compare = this.compareFn;
    const dfs = (node: TreapNode<T> | null, value: T): T | undefined => {
      if (node == null) return undefined;
      if (compare(node.value, value) >= 0) return dfs(node.left, value);

      const tmp = dfs(node.right, value);
      if (tmp == null || compare(node.value, tmp) > 0) {
        return node.value;
      } else {
        return tmp;
      }
    };

    const res = dfs(this.root, value) as any;
    return res === this.leftBound ? undefined : res;
  }

  /**
   *
   * @complexity `O(logn)`
   * @description Find and return the element greater than `val`, return `undefined` if no such element found.
   */
  higher(value: T): T | undefined {
    const compare = this.compareFn;
    const dfs = (node: TreapNode<T> | null, value: T): T | undefined => {
      if (node == null) return undefined;
      if (compare(node.value, value) <= 0) return dfs(node.right, value);

      const tmp = dfs(node.left, value);

      if (tmp == null || compare(node.value, tmp) < 0) {
        return node.value;
      } else {
        return tmp;
      }
    };

    const res = dfs(this.root, value) as any;
    return res === this.rightBound ? undefined : res;
  }

  /**
   *
   * @complexity `O(logn)`
   * @description Find and return the element less than or equal to `val`, return `undefined` if no such element found.
   */
  floor(value: T): T | undefined {
    const compare = this.compareFn;
    const dfs = (node: TreapNode<T> | null, value: T): T | undefined => {
      if (node == null) return undefined;
      if (compare(node.value, value) === 0) return node.value;
      if (compare(node.value, value) >= 0) return dfs(node.left, value);

      const tmp = dfs(node.right, value);
      if (tmp == null || compare(node.value, tmp) > 0) {
        return node.value;
      } else {
        return tmp;
      }
    };

    const res = dfs(this.root, value) as any;
    return res === this.leftBound ? undefined : res;
  }

  /**
   *
   * @complexity `O(logn)`
   * @description Find and return the element greater than or equal to `val`, return `undefined` if no such element found.
   */
  ceil(value: T): T | undefined {
    const compare = this.compareFn;
    const dfs = (node: TreapNode<T> | null, value: T): T | undefined => {
      if (node == null) return undefined;
      if (compare(node.value, value) === 0) return node.value;
      if (compare(node.value, value) <= 0) return dfs(node.right, value);

      const tmp = dfs(node.left, value);

      if (tmp == null || compare(node.value, tmp) < 0) {
        return node.value;
      } else {
        return tmp;
      }
    };

    const res = dfs(this.root, value) as any;
    return res === this.rightBound ? undefined : res;
  }

  /**
   * @complexity `O(logn)`
   * @description
   * Returns the last element from set.
   * If the set is empty, undefined is returned.
   */
  first(): T | undefined {
    const iter = this.inOrder();
    iter.next();
    const res = iter.next().value;
    return res === this.rightBound ? undefined : res;
  }

  /**
   * @complexity `O(logn)`
   * @description
   * Returns the last element from set.
   * If the set is empty, undefined is returned .
   */
  last(): T | undefined {
    const iter = this.reverseInOrder();
    iter.next();
    const res = iter.next().value;
    return res === this.leftBound ? undefined : res;
  }

  /**
   * @complexity `O(logn)`
   * @description
   * Removes the first element from an set and returns it.
   * If the set is empty, undefined is returned and the set is not modified.
   */
  shift(): T | undefined {
    const first = this.first();
    if (first === undefined) return undefined;
    this.delete(first);
    return first;
  }

  /**
   * @complexity `O(logn)`
   * @description
   * Removes the last element from an set and returns it.
   * If the set is empty, undefined is returned and the set is not modified.
   */
  pop(index?: number): T | undefined {
    if (index == null) {
      const last = this.last();
      if (last === undefined) return undefined;
      this.delete(last);
      return last;
    }

    const toDelete = this.at(index);
    if (toDelete == null) return;
    this.delete(toDelete);
    return toDelete;
  }

  /**
   *
   * @complexity `O(logn)`
   * @description
   * Returns number of occurrences of value in the sorted set.
   */
  count(value: T): number {
    const compare = this.compareFn;
    const dfs = (node: TreapNode<T> | null, value: T): number => {
      if (node == null) return 0;
      if (compare(node.value, value) === 0) return node.count;
      if (compare(node.value, value) < 0) return dfs(node.right, value);
      return dfs(node.left, value);
    };

    return dfs(this.root, value);
  }

  *[Symbol.iterator](): Generator<T, any, any> {
    yield* this.values();
  }

  /**
   * @description
   * Returns an iterable of keys in the set.
   */
  *keys(): Generator<T, any, any> {
    yield* this.values();
  }

  /**
   * @description
   * Returns an iterable of values in the set.
   */
  *values(): Generator<T, any, any> {
    const iter = this.inOrder();
    iter.next();
    const steps = this.size;
    for (let _ = 0; _ < steps; _++) {
      yield iter.next().value;
    }
  }

  /**
   * @description
   * Returns a generator for reversed order traversing the set.
   */
  *rvalues(): Generator<T, any, any> {
    const iter = this.reverseInOrder();
    iter.next();
    const steps = this.size;
    for (let _ = 0; _ < steps; _++) {
      yield iter.next().value;
    }
  }

  /**
   * @description
   * Returns an iterable of key, value pairs for every entry in the set.
   */
  *entries(): IterableIterator<[number, T]> {
    const iter = this.inOrder();
    iter.next();
    const steps = this.size;
    for (let i = 0; i < steps; i++) {
      yield [i, iter.next().value];
    }
  }

  private *inOrder(root: TreapNode<T> | null = this.root): Generator<T, any, any> {
    if (root == null) return;
    yield* this.inOrder(root.left);
    const count = root.count;
    for (let _ = 0; _ < count; _++) {
      yield root.value;
    }
    yield* this.inOrder(root.right);
  }

  private *reverseInOrder(root: TreapNode<T> | null = this.root): Generator<T, any, any> {
    if (root == null) return;
    yield* this.reverseInOrder(root.right);
    const count = root.count;
    for (let _ = 0; _ < count; _++) {
      yield root.value;
    }
    yield* this.reverseInOrder(root.left);
  }
}