原文链接: https://leetcode-cn.com/problems/find-the-longest-valid-obstacle-course-at-each-position

英文原文

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 the longest 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 <= 105
• 1 <= obstacles[i] <= 107

中文题目

你打算构建一些障碍赛跑路线。给你一个 下标从 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

通过代码

高赞题解

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

​ 给出一个数组，让我们求每个节点为末尾的最长上升子序列的长度。

​ 最长上升子序列，直接祭出LIS即可。

​ 既然谈到LIS，这里简单讲一下LIS的原理

假设原数组为4， 5， 1， 3， 9

我们可以先预设一个全是INF（无限大）的数组num： INF, INF, INF, INF, INF

然后我们用二分查找依次找出num中第一个大于数组元素的位置，把该位置替换成该元素

遍历到4的时候：

4， INF， INF， INF， INF || 此时以4结尾最长上升子序列长度为1

遍历到5的时候：

4， 5， INF， INF， INF || 此时以5结尾最长上升子序列长度为2

遍历到1的时候：

1， 5， INF， INF， INF || 此时以1结尾最长上升子序列长度为1

遍历到3的时候：

1， 3， INF， INF， INF ||此时以3结尾最长上升子序列长度为2

遍历到9的时候：

1， 3， 9， INF， INF ||此时以9结尾最长上升子序列长度为3

class Solution {
public:
    vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
        const int n = obstacles.size();
        vector<int> ans(n);      //最终答案
        int num[n];              //上升子序列数组
        memset(num, 0x3f, sizeof(num));   //初始化为INF
        for(int i = 0; i < n; ++i){
            auto it = upper_bound(num, num + n, obstacles[i]); //找到第一个比它大的地方
            *it = obstacles[i];        //赋值
            ans[i] = it - num + 1;     //计算当前最大长度
        }
        return ans;
    }
};

统计信息

通过次数	提交次数	AC比率
3259	8401	38.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言