leetcode

Solution to some Leetcode problems written in C++

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

1671.cpp (957B)

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