leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1964.cpp (699B)

      1 class Solution {
      2   public:
      3     vector<int> longestObstacleCourseAtEachPosition(vector<int> &obstacles) {
      4         vector<int> res;
      5         res.reserve(obstacles.size());
      6         vector<int> mono;
      7         mono.reserve(obstacles.size());
      8 
      9         for (int o : obstacles) {
     10             int left = 0, right = mono.size();
     11             while (left < right) {
     12                 int mid = (left + right) / 2;
     13                 if (mono[mid] <= o)
     14                     left = mid + 1;
     15                 else
     16                     right = mid;
     17             }
     18             res.push_back(left + 1);
     19             if (mono.size() == left) mono.push_back(o);
     20             mono[left] = o;
     21         }
     22 
     23         return res;
     24     }
     25 };