leetcode

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

1671.cpp (957B)

      1 class Solution {
      2   public:
      3     int minimumMountainRemovals(const vector<int> &nums) const {
      4         static int left[1001], right[1001];
      5         const int n = size(nums);
      6         vector<int> vec;
      7         int res = 0;
      8 
      9         for (int i = 0; i < n; i++) {
     10             const auto it = lower_bound(begin(vec), end(vec), nums[i]);
     11             left[i] = distance(begin(vec), it);
     12             if (it != end(vec))
     13                 *it = nums[i];
     14             else
     15                 vec.push_back(nums[i]);
     16         }
     17 
     18         vec.clear();
     19         for (int i = n - 1; i >= 0; i--) {
     20             const auto it = lower_bound(begin(vec), end(vec), nums[i]);
     21             right[i] = distance(begin(vec), it);
     22             if (it != end(vec))
     23                 *it = nums[i];
     24             else
     25                 vec.push_back(nums[i]);
     26 
     27             if (!left[i] || !right[i]) continue;
     28             res = max(res, left[i] + right[i]);
     29         }
     30 
     31         return n - res - 1;
     32     }
     33 };