# 1964. Find the Longest Valid Obstacle Course at Each Position
###### tags: `Leetcode` `Hard` `Greedy` `Longest Increasing Subsequence`
Link: https://leetcode.com/problems/find-the-longest-valid-obstacle-course-at-each-position/description/
## 思路
由于时间复杂度的限制 这道题只能用greedy做 也就是类似[0300. Longest Increasing Subsequence](https://hackmd.io/oPc5yL1oRhGtGP8UdRd3_g)的方法做
我们每次把```num```插在```lis```的哪个位置 那么```idx+1```就是目前的LIS长度
## Code

class Solution {
    public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
        int n = obstacles.length;
        int[] ans = new int[n];
        List<Integer> lis = new ArrayList<>();
        for(int i=0; i<obstacles.length; i++){
            int num = obstacles[i];
            if(lis.size()==0 || num>=lis.get(lis.size()-1)){
                lis.add(num);
                ans[i] = lis.size();
            }
            else{
                int start = 0;
                int end = lis.size()-1;
                while(start<end){
                    int mid = start+(end-start)/2;
                    if(lis.get(mid)<=num) start = mid+1;
                    else end = mid;
                }
                lis.set(start, num);
                ans[i] = start+1;
            }
        }
        return ans;
    }
}