二分与贪心建模

最长递增子序列的长度如何用二分求解？

• 维护数组 tails, tails[i] 表示长度为 i+1 的递增子序列的最小末尾值;
• 遍历元素 num:
  • num 大于 tails 末尾: 直接追加, 最长长度加一;
  • 否则二分找到首个大于等于 num 的位置, 用 num 覆盖它;
• tails 本身不是某个具体子序列, 只用于保持"同长度下末尾尽量小";
• 结束时 tails 的长度即最长递增子序列的长度;

function lengthOfLIS(nums: number[]): number {
  const tails: number[] = [nums[0]];
  for (let i = 1; i < nums.length; i++) {
    const num = nums[i];
    if (num > tails[tails.length - 1]) {
      tails.push(num);
      continue;
    }
    let left = 0;
    let right = tails.length;
    while (left < right) {
      const mid = Math.floor(left + (right - left) / 2);
      if (num <= tails[mid]) right = mid;
      else left = mid + 1;
    }
    tails[left] = num;
  }
  return tails.length;
}

• 时间复杂度: O(n log n);
• 空间复杂度: O(n);

数据流的中位数如何维护？

• 做法一: 维护有序数组, 插入时用二分找位置再 splice;
  • 二分定位 O(log n), 但数组搬移插入 O(n), 查询 O(1);
• 做法二: 用一个小顶堆和一个大顶堆各保存一半元素;
  • 小顶堆放较大的一半, 大顶堆放较小的一半;
  • 插入时先压入另一半的堆, 再取出堆顶回填, 保证两堆大小差不超过 1;
  • 数量相等时中位数为两堆顶的平均, 否则为小顶堆的堆顶;
  • 插入与查询均为 O(log n);

class MedianFinder {
  private sorted: number[] = [];

  addNum(num: number): void {
    let left = 0;
    let right = this.sorted.length;
    while (left < right) {
      const mid = Math.floor(left + (right - left) / 2);
      if (this.sorted[mid] < num) left = mid + 1;
      else right = mid;
    }
    this.sorted.splice(left, 0, num);
  }

  findMedian(): number {
    const mid = Math.floor((this.sorted.length - 1) / 2);
    if (this.sorted.length % 2 === 1) return this.sorted[mid];
    return (this.sorted[mid] + this.sorted[mid + 1]) / 2;
  }
}