Find the Longest Valid Obstacle Course at Each Position LeetCode solution in Java

1
class Solution {
2
  public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
3
    int i = -1, cur = 0, lisSize = -1;
4
    int[] lis = new int[obstacles.length];
5
    int[] ans = new int[obstacles.length];
6

7
    for (int curHeight : obstacles) {
8
      if (i == -1 || lis[i] <= curHeight) {
9
        lis[++i] = curHeight;
10
        lisSize = i;
11
      } else {
12
        lisSize = search(lis, 0, i, curHeight);
13
        lis[lisSize] = curHeight;
14
      }
15

16
      ans[cur++] = lisSize + 1;
17
    }
18

19
    return ans;
20
  }
21

22
  private int search(int[] nums, int start, int end, int target) {
23
    int left = start, right = end;
24
    int boundary = 0;
25
    while (left <= right) {
26
      int mid = left + (right - left) / 2;
27
      if (nums[mid] > target) {
28
        boundary = mid;
29
        right = mid - 1;
30
      } else left = mid + 1;
31
    }
32
    return boundary;
33
  }
34
}