1964. Find the Longest Valid Obstacle Course at Each Position

Question

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.

Solution

类似于300. Longest Increasing Subsequence

每个位置i的最大长度等于之前小于或等于当前值的位置j对应的长度再加一。（类似动态规划）

储存一个size[len]数组保存长度为len的递增子数组的最小障碍高度obstacles[i]。

由于保存的是每个len最小障碍高度，因此size[len]随着len的增长单调不递减。（如果size[len] = a > size[len+1] b，则b一定可以组成最小子数列size[len]）

如果Brute Force搜索，则需要O(n2)复杂度。

由于单调不递减，因此可以使用二分搜索优化查找过程为O(nlogn)。

Code

class Solution {
    public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
        int n = obstacles.length;
        int[] ret = new int[n];
        int[] size = new int[n+1];
 
        for(int i = 0; i < n; i++){
            size[i] = Integer.MAX_VALUE;
        }
        size[0] = 0;
        for(int i = 0; i < n; i++){
            int cur = obstacles[i];
            int left = 0, right = n - 1;
            int ans = 0;
            while(left <= right){
                int mid = (left + right)/2; 
                if(size[mid] > cur){
                    right = mid - 1;
                }
                else{
                    ans = mid;
                    left = mid + 1;
                }
            }
            ret[i] = ans + 1;
            size[ret[i]] = Math.min(size[ret[i]], cur);
        }
        return ret;
    }
}