{"id":5537,"date":"2019-09-07T21:33:58","date_gmt":"2019-09-08T04:33:58","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5537"},"modified":"2019-09-08T19:09:11","modified_gmt":"2019-09-09T02:09:11","slug":"leetcode-1187-make-array-strictly-increasing","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1187-make-array-strictly-increasing\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1187. Make Array Strictly Increasing"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1187. Make Array Strictly Increasing - \u5237\u9898\u627e\u5de5\u4f5c EP288\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/8ttxdMCU2GE?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>Given two integer arrays&nbsp;<code>arr1<\/code>&nbsp;and&nbsp;<code>arr2<\/code>, return the minimum number of operations (possibly zero) needed&nbsp;to make&nbsp;<code>arr1<\/code>&nbsp;strictly increasing.<\/p>\n\n\n\n<p>In one operation, you can choose two indices&nbsp;<code>0 &lt;=&nbsp;i &lt; arr1.length<\/code>&nbsp;and&nbsp;<code>0 &lt;= j &lt; arr2.length<\/code>&nbsp;and do the assignment&nbsp;<code>arr1[i] = arr2[j]<\/code>.<\/p>\n\n\n\n<p>If there is no way to make&nbsp;<code>arr1<\/code>&nbsp;strictly increasing,&nbsp;return&nbsp;<code>-1<\/code>.<\/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> arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]\n<strong>Output:<\/strong> 1\n<strong>Explanation:<\/strong> Replace <code>5<\/code> with <code>2<\/code>, then <code>arr1 = [1, 2, 3, 6, 7]<\/code>.\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> arr1 = [1,5,3,6,7], arr2 = [4,3,1]\n<strong>Output:<\/strong> 2\n<strong>Explanation:<\/strong> Replace <code>5<\/code> with <code>3<\/code> and then replace <code>3<\/code> with <code>4<\/code>. <code>arr1 = [1, 3, 4, 6, 7]<\/code>.\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> arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]\n<strong>Output:<\/strong> -1\n<strong>Explanation:<\/strong> You can't make <code>arr1<\/code> strictly increasing.<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= arr1.length, arr2.length &lt;= 2000<\/code><\/li><li><code>0 &lt;= arr1[i], arr2[i] &lt;= 10^9<\/code><\/li><\/ul>\n\n\n\n<p><strong>Solution: DP<\/strong><\/p>\n\n\n\n<p>Time complexity: O(mn)<br>Space complexity: O(mn) -&gt; O(m + 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 makeArrayIncreasing(vector<int>& a, vector<int>& c) {\n    constexpr int kInf = 1e9;\n    int m = a.size();    \n    \/\/ Sort b and make it only containing unique numbers.\n    sort(begin(c), end(c));\n    vector<int> b;\n    for (int i = 0; i < c.size(); ++i) {\n      if (!b.empty() &#038;&#038; c[i] == b.back()) continue;\n      b.push_back(c[i]);\n    }    \n    int n = b.size();\n    \n    \/\/ min steps to make a[0~i] valid by keeping a[i]\n    vector<int> keep(m, kInf);\n    keep[0] = 0;\n    \/\/ swap[i][j] := min steps to make a[0~i] valid by a[i] = b[j]\n    vector<int> swap(n, 1);\n    \n    for (int i = 1; i < m; ++i) {\n      int min_keep = kInf;\n      int min_swap = kInf;\n      vector<int> temp(n, kInf);\n      for (int j = 0; j < n; ++j) {\n        if (j > 0) min_swap = min(min_swap, swap[j - 1] + 1);\n        if (a[i] > b[j]) min_keep = min(min_keep, swap[j]);        \n        if (a[i] > a[i - 1]) keep[i] = keep[i - 1];\n        if (b[j] > a[i - 1]) temp[j] = keep[i - 1] + 1;        \n        temp[j] = min(temp[j], min_swap);\n        keep[i] = min(keep[i], min_keep);\n      }\n      temp.swap(swap);\n    }\n    \n    int s = *min_element(begin(swap), end(swap));\n    int k = keep.back();\n    int ans = min(s, k);\n    return ans >= kInf ? -1 : ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given two integer arrays&nbsp;arr1&nbsp;and&nbsp;arr2, return the minimum number of operations (possibly zero) needed&nbsp;to make&nbsp;arr1&nbsp;strictly increasing. In one operation, you can choose two indices&nbsp;0 &lt;=&nbsp;i &lt;&#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,290],"class_list":["post-5537","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-hard","tag-swap","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5537","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=5537"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5537\/revisions"}],"predecessor-version":[{"id":5543,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5537\/revisions\/5543"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5537"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5537"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5537"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}