Skip to content

Latest commit

 

History

History
203 lines (161 loc) · 7.21 KB

1964.md

File metadata and controls

203 lines (161 loc) · 7.21 KB
title description keywords
1964. 找出到每个位置为止最长的有效障碍赛跑路线
LeetCode 1964. 找出到每个位置为止最长的有效障碍赛跑路线题解，Find the Longest Valid Obstacle Course at Each Position，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。
LeetCode
1964. 找出到每个位置为止最长的有效障碍赛跑路线
找出到每个位置为止最长的有效障碍赛跑路线
Find the Longest Valid Obstacle Course at Each Position
解题思路
树状数组
数组
二分查找

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

🔴 Hard  🔖  树状数组 数组 二分查找  🔗 力扣 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 最长递增子序列 [✓] 数组 二分查找 动态规划 🟠 🀄️ 🔗