Question

1964. 找出到每个位置为止最长的有效障碍赛跑路线

English Version

题目描述

你打算构建一些障碍赛跑路线。给你一个 下标从 0 开始 的整数数组 obstacles ，数组长度为 n ，其中 obstacles[i] 表示第 i 个障碍的高度。

对于每个介于 0 和 n - 1 之间（包含 0 和 n - 1）的下标  i ，在满足下述条件的前提下，请你找出 obstacles 能构成的最长障碍路线的长度：

• 你可以选择下标介于 0 到 i 之间（包含 0 和 i）的任意个障碍。
• 在这条路线中，必须包含第 i 个障碍。
• 你必须按障碍在 obstacles 中的 出现顺序 布置这些障碍。
• 除第一个障碍外，路线中每个障碍的高度都必须和前一个障碍 相同 或者 更高 。

返回长度为 n 的答案数组 ans ，其中 ans[i] 是上面所述的下标 i 对应的最长障碍赛跑路线的长度。

 

示例 1：

输入：obstacles = [1,2,3,2]
输出：[1,2,3,3]
解释：每个位置的最长有效障碍路线是：
- i = 0: [_1_], [1] 长度为 1
- i = 1: [_1_,_2_], [1,2] 长度为 2
- i = 2: [_1_,_2_,_3_], [1,2,3] 长度为 3
- i = 3: [_1_,_2_,3,_2_], [1,2,2] 长度为 3

示例 2：

输入：obstacles = [2,2,1]
输出：[1,2,1]
解释：每个位置的最长有效障碍路线是：
- i = 0: [_2_], [2] 长度为 1
- i = 1: [_2_,_2_], [2,2] 长度为 2
- i = 2: [2,2,_1_], [1] 长度为 1

示例 3：

输入：obstacles = [3,1,5,6,4,2]
输出：[1,1,2,3,2,2]
解释：每个位置的最长有效障碍路线是：
- i = 0: [_3_], [3] 长度为 1
- i = 1: [3,_1_], [1] 长度为 1
- i = 2: [_3_,1,_5_], [3,5] 长度为 2, [1,5] 也是有效的障碍赛跑路线
- i = 3: [_3_,1,_5_,_6_], [3,5,6] 长度为 3, [1,5,6] 也是有效的障碍赛跑路线
- i = 4: [_3_,1,5,6,_4_], [3,4] 长度为 2, [1,4] 也是有效的障碍赛跑路线
- i = 5: [3,_1_,5,6,4,_2_], [1,2] 长度为 2

 

提示：

• n == obstacles.length
• 1 <= n <= 105
• 1 <= obstacles[i] <= 107

解法

方法一：树状数组

我们可以用树状数组维护一个最长递增子序列的长度数组。

然后对于每个障碍，我们在树状数组中查询小于等于当前障碍的最长递增子序列的长度，假设为 $l$，那么当前障碍的最长递增子序列的长度为 $l+1$，我们将 $l+1$ 添加到答案数组中，并将 $l+1$ 更新到树状数组。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为障碍的数量。

class BinaryIndexedTree:
  __slots__ = ["n", "c"]

  def __init__(self, n: int):
    self.n = n
    self.c = [0] * (n + 1)

  def update(self, x: int, v: int):
    while x <= self.n:
      self.c[x] = max(self.c[x], v)
      x += x & -x

  def query(self, x: int) -> int:
    s = 0
    while x:
      s = max(s, self.c[x])
      x -= x & -x
    return s


class Solution:
  def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
    nums = sorted(set(obstacles))
    n = len(nums)
    tree = BinaryIndexedTree(n)
    ans = []
    for x in obstacles:
      i = bisect_left(nums, x) + 1
      ans.append(tree.query(i) + 1)
      tree.update(i, ans[-1])
    return ans

class BinaryIndexedTree {
  private int n;
  private int[] c;

  public BinaryIndexedTree(int n) {
    this.n = n;
    c = new int[n + 1];
  }

  public void update(int x, int v) {
    while (x <= n) {
      c[x] = Math.max(c[x], v);
      x += x & -x;
    }
  }

  public int query(int x) {
    int s = 0;
    while (x > 0) {
      s = Math.max(s, c[x]);
      x -= x & -x;
    }
    return s;
  }
}

class Solution {
  public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
    int[] nums = obstacles.clone();
    Arrays.sort(nums);
    int n = nums.length;
    int[] ans = new int[n];
    BinaryIndexedTree tree = new BinaryIndexedTree(n);
    for (int k = 0; k < n; ++k) {
      int x = obstacles[k];
      int i = Arrays.binarySearch(nums, x) + 1;
      ans[k] = tree.query(i) + 1;
      tree.update(i, ans[k]);
    }
    return ans;
  }
}

class BinaryIndexedTree {
private:
  int n;
  vector<int> c;

public:
  BinaryIndexedTree(int n) {
    this->n = n;
    c = vector<int>(n + 1);
  }

  void update(int x, int v) {
    while (x <= n) {
      c[x] = max(c[x], v);
      x += x & -x;
    }
  }

  int query(int x) {
    int s = 0;
    while (x > 0) {
      s = max(s, c[x]);
      x -= x & -x;
    }
    return s;
  }
};

class Solution {
public:
  vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
    vector<int> nums = obstacles;
    sort(nums.begin(), nums.end());
    int n = nums.size();
    vector<int> ans(n);
    BinaryIndexedTree tree(n);
    for (int k = 0; k < n; ++k) {
      int x = obstacles[k];
      auto it = lower_bound(nums.begin(), nums.end(), x);
      int i = distance(nums.begin(), it) + 1;
      ans[k] = tree.query(i) + 1;
      tree.update(i, ans[k]);
    }
    return ans;
  }
};

type BinaryIndexedTree struct {
  n int
  c []int
}

func NewBinaryIndexedTree(n int) *BinaryIndexedTree {
  return &BinaryIndexedTree{n, make([]int, n+1)}
}

func (bit *BinaryIndexedTree) update(x, v int) {
  for x <= bit.n {
    bit.c[x] = max(bit.c[x], v)
    x += x & -x
  }
}

func (bit *BinaryIndexedTree) query(x int) (s int) {
  for x > 0 {
    s = max(s, bit.c[x])
    x -= x & -x
  }
  return
}

func longestObstacleCourseAtEachPosition(obstacles []int) (ans []int) {
  nums := slices.Clone(obstacles)
  sort.Ints(nums)
  n := len(nums)
  tree := NewBinaryIndexedTree(n)
  for k, x := range obstacles {
    i := sort.SearchInts(nums, x) + 1
    ans = append(ans, tree.query(i)+1)
    tree.update(i, ans[k])
  }
  return
}

class BinaryIndexedTree {
  private n: number;
  private c: number[];

  constructor(n: number) {
    this.n = n;
    this.c = Array(n + 1).fill(0);
  }

  update(x: number, v: number): void {
    while (x <= this.n) {
      this.c[x] = Math.max(this.c[x], v);
      x += x & -x;
    }
  }

  query(x: number): number {
    let s = 0;
    while (x > 0) {
      s = Math.max(s, this.c[x]);
      x -= x & -x;
    }
    return s;
  }
}

function longestObstacleCourseAtEachPosition(obstacles: number[]): number[] {
  const nums: number[] = [...obstacles];
  nums.sort((a, b) => a - b);
  const n: number = nums.length;
  const ans: number[] = [];
  const tree: BinaryIndexedTree = new BinaryIndexedTree(n);
  const search = (x: number): number => {
    let [l, r] = [0, n];
    while (l < r) {
      const mid = (l + r) >> 1;
      if (nums[mid] >= x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  };
  for (let k = 0; k < n; ++k) {
    const i: number = search(obstacles[k]) + 1;
    ans[k] = tree.query(i) + 1;
    tree.update(i, ans[k]);
  }
  return ans;
}