Leetcode-1964: find the longest effective obstacle race route to each position

subject

Topic linking
You plan to build some obstacle race routes . To give you one Subscript from 0 Start Array of integers for obstacles , The array length is n , among obstacles[i] It means the first one i The height of obstacles .

For each between 0 and n - 1 Between （ contain 0 and n - 1） The subscript i , On the premise that the following conditions are met , Please find out obstacles The length of the longest obstacle route that can be formed ：

• You can choose a subscript between 0 To i Between （ contain 0 and i） Any obstacle of .
• In this route , Must include section i There's a barrier .
• You must press the barrier in obstacles Medium The order of appearance Arrange these obstacles .
• Except for the first obstacle , The height of each obstacle in the route must be the same as the previous obstacle identical perhaps Higher .
  Return length is n The answer array of ans , among ans[i] Is the subscript mentioned above i The length of the corresponding longest obstacle race route .

Example 1：

 Input ：obstacles = [1,2,3,2]
 Output ：[1,2,3,3]
 explain ： The longest effective obstacle route for each location is ：
- i = 0: [1], [1]  The length is  1
- i = 1: [1,2], [1,2]  The length is  2
- i = 2: [1,2,3], [1,2,3]  The length is  3
- i = 3: [1,2,3,2], [1,2,2]  The length is  3

Example 2：

 Input ：obstacles = [2,2,1]
 Output ：[1,2,1]
 explain ： The longest effective obstacle route for each location is ：
- i = 0: [2], [2]  The length is  1
- i = 1: [2,2], [2,2]  The length is  2
- i = 2: [2,2,1], [1]  The length is  1

Example 3：

 Input ：obstacles = [3,1,5,6,4,2]
 Output ：[1,1,2,3,2,2]
 explain ： The longest effective obstacle route for each location is ：
- i = 0: [3], [3]  The length is  1
- i = 1: [3,1], [1]  The length is  1
- i = 2: [3,1,5], [3,5]  The length is  2, [1,5]  It is also an effective obstacle race route 
- i = 3: [3,1,5,6], [3,5,6]  The length is  3, [1,5,6]  It is also an effective obstacle race route 
- i = 4: [3,1,5,6,4], [3,4]  The length is  2, [1,4]  It is also an effective obstacle race route 
- i = 5: [3,1,5,6,4,2], [1,2]  The length is  2

Problem solving

This question , At first glance, it's actually with leetcode-300： The longest increasing subsequence Same , But for this problem $O(n^2)$ The method of will timeout , Therefore, we need a method with lower time complexity

Method 1 ： Dynamic programming + Two points search

Reference link

MinVals[i]：i Indicates that the length of the current built is i The length of the obstacle route ,MinVals[i] The length is i The height of the last obstacle of the obstacle length .

Then you can traverse the obstacles , And MinVals[i] Just compare , If you are taller than him , So the result is MinVals[i]+1. because Minvals[i] Is a non strictly increasing array , So you can use binary search , Reduce time complexity to $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);// structure i Minimum obstacle height value of length .
        MinVals[0]=INT_MIN;
        for(int i=0;i<n;i++){
    
            // Two points search （ Find the longest , And the obstacle height is less than obstacles[i]）
            int l=0,r=i+1;//i+1 Is the maximum length that can be reached 
            while(l<r){
    
                int mid=(l+r)/2;
                if(obstacles[i]<MinVals[mid]) r=mid;
                else l=mid+1;// Equal or equal to , Should look for a longer length 
            }// So the final result is l Is the length that has been built +1
            res.push_back(l);
            MinVals[l]=min(MinVals[l],obstacles[i]);
        }
        return res;

    }
};