{"id":7729,"date":"2020-11-28T13:08:42","date_gmt":"2020-11-28T21:08:42","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7729"},"modified":"2020-11-28T13:09:34","modified_gmt":"2020-11-28T21:09:34","slug":"leetcode-1671-minimum-number-of-removals-to-make-mountain-array","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1671-minimum-number-of-removals-to-make-mountain-array\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1671. Minimum Number of Removals to Make Mountain Array"},"content":{"rendered":"\n<p>You may recall that an array&nbsp;<code>arr<\/code>&nbsp;is a&nbsp;<strong>mountain array<\/strong>&nbsp;if and only if:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>arr.length &gt;= 3<\/code><\/li><li>There exists some index&nbsp;<code>i<\/code>&nbsp;(<strong>0-indexed<\/strong>) with&nbsp;<code>0 &lt; i &lt; arr.length - 1<\/code>&nbsp;such that:<ul><li><code>arr[0] &lt; arr[1] &lt; ... &lt; arr[i - 1] &lt; arr[i]<\/code><\/li><li><code>arr[i] &gt; arr[i + 1] &gt; ... &gt; arr[arr.length - 1]<\/code><\/li><\/ul><\/li><\/ul>\n\n\n\n<p>Given an integer array&nbsp;<code>nums<\/code>\u200b\u200b\u200b, return&nbsp;<em>the&nbsp;<strong>minimum<\/strong>&nbsp;number of elements to remove to make&nbsp;<\/em><code>nums<em>\u200b\u200b\u200b<\/em><\/code><em>a&nbsp;<strong>mountain array<\/strong>.<\/em><\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [1,3,1]\n<strong>Output:<\/strong> 0\n<strong>Explanation:<\/strong> The array itself is a mountain array so we do not need to remove any elements.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [2,1,1,5,6,2,3,1]\n<strong>Output:<\/strong> 3\n<strong>Explanation:<\/strong> One solution is to remove the elements at indices 0, 1, and 5, making the array nums = [1,5,6,3,1].\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [4,3,2,1,1,2,3,1]\n<strong>Output:<\/strong> 4\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [1,2,3,4,4,3,2,1]\n<strong>Output:<\/strong> 1\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>3 &lt;= nums.length &lt;= 1000<\/code><\/li><li><code>1 &lt;= nums[i] &lt;= 10<sup>9<\/sup><\/code><\/li><li>It is guaranteed that you can make a mountain array out of&nbsp;<code>nums<\/code>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: DP \/ LIS<\/strong><\/h2>\n\n\n\n<p>LIS[i] := longest increasing subsequence ends with nums[i]<br>LDS[i] := longest decreasing subsequence starts with nums[i]<br>Let nums[i] be the peak, the length of the mountain array is LIS[i] + LDS[i] &#8211; 1<br>Note: LIS[i] and LDS[i] must be &gt; 1 to form a valid mountain array.<br>ans = min(n &#8211; (LIS[i] + LDS[i] &#8211; 1)) 0 &lt;= i &lt; n<\/p>\n\n\n\n<p>Time complexity: O(n^2)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int minimumMountainRemovals(vector<int>& nums) {\n    const int n = nums.size();\n    vector<int> LIS(n, 1); \/\/ LIS[i] := Longest increasing subseq ends with nums[i]\n    vector<int> LDS(n, 1); \/\/ LDS[i] := Longest decreasing subseq starts with nums[i]\n    for (int i = 0; i < n; ++i)      \n      for (int j = 0; j < i; ++j)\n        if (nums[i] > nums[j]) LIS[i] = max(LIS[i], LIS[j] + 1);\n    for (int i = n - 1; i >= 0; --i)\n      for (int j = n - 1; j > i; --j)\n        if (nums[i] > nums[j]) LDS[i] = max(LDS[i], LDS[j] + 1);\n    int ans = INT_MAX;\n    for (int i = 0; i < n; ++i) {\n      if (LIS[i] < 2 || LDS[i] < 2) continue;\n      ans = min(ans, n - (LIS[i] + LDS[i] - 1));\n    }\n    return ans;\n  }\n};\n\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You may recall that an array&nbsp;arr&nbsp;is a&nbsp;mountain array&nbsp;if and only if: arr.length &gt;= 3 There exists some index&nbsp;i&nbsp;(0-indexed) with&nbsp;0 &lt; i &lt; arr.length &#8211; 1&nbsp;such&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,217,69,672],"class_list":["post-7729","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-hard","tag-lis","tag-mountain-array","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7729","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7729"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7729\/revisions"}],"predecessor-version":[{"id":7731,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7729\/revisions\/7731"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7729"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7729"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7729"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}