2774. 数组上界(二分和双指针)

2774. 数组的上界

interface Array<T> {
  upperBound(target: number): number
}


/**
 * 二分法
 * 时间复杂度: O(log n) 
 * 空间复杂度: O(1) 没有使用额外空间
 */
Array.prototype.upperBound = function (target: number): number {
    let left = 0, right = this.length - 1;
    let result = -1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (this[mid] === target) {
            result = mid;
            left = mid + 1; // 向右查找更新更大的索引
        } else if (this[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

/**
 * 遍历
 * 时间复杂度: O(n) 最坏情况下需要遍历整个字符串
 * 空间复杂度: O(1) 没有使用额外空间
 */
Array.prototype.upperBound = function(target) {
  for(let i = this.length - 1; i >= 0; i--) {
    if(target === this[i]) return i
  }
  return -1;
};


/**
 * 双指针遍历
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */
Array.prototype.upperBound = function (target): number {
  if (this.length == 0) return -1
  let i = 0
  let l = this.length - 1
  let upperIndex = -1
  while (i <= l) {
    if (this[l] === target) return l
    if (this[i] > target) return upperIndex;
    if (this[i] === target) {
      if (i > upperIndex) upperIndex = i
    }
    i++;
    l--;
  }
  return upperIndex;
}

/**
 * js  数原生方法
 * 时间复杂度: O(n) 最坏情况下需要遍历整个字符串
 * 空间复杂度: O(1) 没有使用额外空间
 */
Array.prototype.upperBound = function(target) {
  return this.lastIndexOf(target);
};

题目要点

「2774. 数组上界(二分和双指针)」的关键不是把流程写出来，而是先定义序列不变量，并确保每一次遍历/交换都不会破坏该不变量。

思路拆解

1. 明确状态含义：当前索引、窗口边界、候选答案分别表示什么。
2. 先给出直观解法，再说明为什么需要优化到目标复杂度。
3. 逐步引入数据结构（Set/Map/双指针/二分）来消除重复扫描。

复杂度分析

• 时间复杂度：以代码实现为准，核心取决于是否存在重复遍历或嵌套回扫。
• 空间复杂度：重点关注辅助集合与中间数组的规模是否与输入同阶。

边界与测试

1. 空数组、单元素、全部重复值。
2. 单调序列、逆序序列、已满足条件的输入。
3. 极值与退化场景（如大量重复导致分支频繁命中）。

工程实践

将“状态转移条件”写成可读的布尔表达式，并在关键分支补充注释，方便后续重构与复盘。

总结

这类数组题的复用价值在于沉淀不变量模板：先定约束，再定遍历策略，最后用复杂度与边界用例验证正确性。