leetcode

0 class Solution {

1 public:

2 vector<int> longestObstacleCourseAtEachPosition(vector<int> &obstacles) {

3 vector<int> res;

4 res.reserve(obstacles.size());

5 vector<int> mono;

6 mono.reserve(obstacles.size());

7

8 for (int o : obstacles) {

9 int left = 0, right = mono.size();

10 while (left < right) {

11 int mid = (left + right) / 2;

12 if (mono[mid] <= o)

13 left = mid + 1;

14 else

15 right = mid;

16 }

17 res.push_back(left + 1);

18 if (mono.size() == left) mono.push_back(o);

19 mono[left] = o;

20 }

21

22 return res;

23 }

24 };