leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1964.cpp (699B)

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 };