题目

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

1
2
3
4
5
6
7
8

示例 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

1
2
3
4
5
6
7

示例 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

1
2
3
4
5
6
7
8
9
10

解题

这道题，一看其实是和leetcode-300：最长递增子序列一样的，但是对于这道题$O(n^2)$的方法会超时，因此要使用更加速度快的方法

方法一：动态规划+二分查找

参考链接

MinVals[i]：i表示当前已经构建的长度为i的障碍物路线长度，MinVals[i]表示长度为i的障碍物长度的最后一个障碍物的高度。

那么就可以遍历障碍物，与MinVals[i]比就行了，如果比他高，那么结果就是MinVals[i]+1。由于Minvals[i]是一个非严格递增的数组，因此可以使用二分查找，将时间复杂度降低为$O(nlo{g}_{2}n)$

class Solution {
public:
    vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
        int n=obstacles.size();
        vector<int> res;
        vector<int> MinVals(n+1,INT_MAX);//构建i长度的最小的障碍物高度值。
        MinVals[0]=INT_MIN;
        for(int i=0;i<n;i++){
            //二分查找（找到长度最大的，且障碍高度小于obstacles[i]）
            int l=0,r=i+1;//i+1就是所能达到的最大长度
            while(l<r){
                int mid=(l+r)/2;
                if(obstacles[i]<MinVals[mid]) r=mid;
                else l=mid+1;//相等或者等于，都应该去找更长的长度
            }//因此最终得到的l是已经构建的长度+1
            res.push_back(l);
            MinVals[l]=min(MinVals[l],obstacles[i]);
        }
        return res;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22