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

🔴   🔖  树状数组 数组 二分查找  🔗 力扣 LeetCode

题目

You want to build some obstacle courses. You are given a 0-indexed integer array obstacles of length n, where obstacles[i] describes the height of the ith obstacle.

For every index i between 0 and n - 1 (inclusive), find the length of the longest obstacle course in obstacles such that:

• You choose any number of obstacles between 0 and i inclusive.
• You must include the ith obstacle in the course.
• You must put the chosen obstacles in the same order as they appear in obstacles.
• Every obstacle (except the first) is taller than or the same height as the obstacle immediately before it.

Return an array ans of length n, where ans[i] is the length of thelongest obstacle course for index i as described above.

Example 1:

Input: obstacles = [1,2,3,2]

Output: [1,2,3,3]

Explanation: The longest valid obstacle course at each position is:

• i = 0: [1], [1] has length 1.
• i = 1: [1 ,2], [1,2] has length 2.
• i = 2: [1 ,2 ,3], [1,2,3] has length 3.
• i = 3: [1 ,2 ,3,2], [1,2,2] has length 3.

Example 2:

Input: obstacles = [2,2,1]

Output: [1,2,1]

Explanation: The longest valid obstacle course at each position is:

• i = 0: [2], [2] has length 1.
• i = 1: [2 ,2], [2,2] has length 2.
• i = 2: [2,2,1], [1] has length 1.

Example 3:

Input: obstacles = [3,1,5,6,4,2]

Output: [1,1,2,3,2,2]

Explanation: The longest valid obstacle course at each position is:

• i = 0: [3], [3] has length 1.
• i = 1: [3,1], [1] has length 1.
• i = 2: [3 ,1,5], [3,5] has length 2. [1,5] is also valid.
• i = 3: [3 ,1,5 ,6], [3,5,6] has length 3. [1,5,6] is also valid.
• i = 4: [3 ,1,5,6,4], [3,4] has length 2. [1,4] is also valid.
• i = 5: [3,1 ,5,6,4,2], [1,2] has length 2.

Constraints:

• n == obstacles.length
• 1 <= n <= 10^5
• 1 <= obstacles[i] <= 10^7

题目大意

你打算构建一些障碍赛跑路线。给你一个 下标从 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 <= 10^5
• 1 <= obstacles[i] <= 10^7

解题思路

1. 定义 tails 数组：

   • tails[i] 表示长度为 i+1 的最长非递减子序列的最小结尾元素。
   • len 记录 tails 当前有效的长度。

2. 遍历 obstacles 并维护 tails：

   • 通过二分查找找到 obstacles[i] 在 tails 中的插入位置：
     • 如果 tails[mid] ≤ obstacles[i]，说明可以延长 LIS，移动 left 继续查找更大的位置。
     • 否则，更新 right 收缩范围。
   • 更新 tails：
     • 如果 left == len，说明 obstacles[i] 比 tails 所有元素都大，直接新增一个 LIS 元素。
     • 否则，更新 tails[left]，替换已有的更大元素。

3. 记录结果：

   • result[i] = left + 1，表示当前位置的 LIS 长度。

复杂度分析

• 时间复杂度：O(n log n)，其中 n 是 obstacles 数组的长度。
  • 遍历 obstacles：O(n)。
  • 二分查找更新 tails：每次 O(log n)。
  • 总复杂度：O(n log n)。
• 空间复杂度：O(n)，需要额外的空间来存储辅助数组。

代码

/**
 * @param {number[]} obstacles
 * @return {number[]}
 */
var longestObstacleCourseAtEachPosition = function (obstacles) {
	let result = [];
	let tails = [];

	for (let i = 0; i < obstacles.length; i++) {
		let left = 0,
			right = tails.length;
		while (left < right) {
			let mid = Math.floor((left + right) / 2);
			if (tails[mid] <= obstacles[i]) left = mid + 1;
			else right = mid;
		}
		if (left === tails.length) tails.push(obstacles[i]);
		else tails[left] = obstacles[i];
		result.push(left + 1);
	}

	return result;
};

相关题目

题号	标题	题解	标签	难度	力扣
300	最长递增子序列	[✓]	数组 二分查找 动态规划	🟠	🀄️ 🔗