LeetCode
comments powered by Disqus
Editorial: LeetCode 1671 Minimum Number of Removals to Make Mountain Array
https://leetcode.com/problems/minimum-number-of-removals-to-make-mountain-array/ from Microsoft
Thinking process:
Very similar to this question: https://leetcode.com/problems/longest-increasing-subsequence/, where we only need to consider one direction. Here, we need to consider two directions. Basically like below.
So, in the code, we scan twice, from left to right and from right to left. The only thing needs to be careful is that, when we calculate the final answer, we can’t count the first element (0 index) and the last element because it’s never a mountain if our peak is at that position.
1class Solution {
2public:
3 vector<int> left, right;
4 void build(vector<int>& nums, int start, int end, int off, vector<int>& target) {
5 vector<int> q;
6 int cnt = 0;
7 int i = start;
8 while (i != end) {
9 cnt++;
10 auto it = lower_bound(q.begin(), q.end(), nums[i]);
11 if (it == q.end())
12 q.push_back(nums[i]);
13 else
14 *it = nums[i];
15 target[i] = (cnt - q.size());
16 i += off;
17 }
18 }
19 int minimumMountainRemovals(vector<int>& nums) {
20 int N = nums.size();
21 left.resize(N);
22 right.resize(N);
23 build(nums, 0, N, 1, left);
24 build(nums, N-1, -1, -1, right);
25 int ans = N;
26 for (int i=1; i<N-1; i++) {
27 ans = min(ans, left[i] + right[i]);
28 }
29 return ans;
30 }
31};