{"id":8523,"date":"2021-08-08T16:19:51","date_gmt":"2021-08-08T23:19:51","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8523"},"modified":"2021-08-08T16:21:19","modified_gmt":"2021-08-08T23:21:19","slug":"leetcode-1881-maximum-value-after-insertion","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-1881-maximum-value-after-insertion\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1881. Maximum Value after Insertion"},"content":{"rendered":"\n<p>You are given a very large integer&nbsp;<code>n<\/code>, represented as a string,\u200b\u200b\u200b\u200b\u200b\u200b and an integer digit&nbsp;<code>x<\/code>. The digits in&nbsp;<code>n<\/code>&nbsp;and the digit&nbsp;<code>x<\/code>&nbsp;are in the&nbsp;<strong>inclusive<\/strong>&nbsp;range&nbsp;<code>[1, 9]<\/code>, and&nbsp;<code>n<\/code>&nbsp;may represent a&nbsp;<strong>negative<\/strong>&nbsp;number.<\/p>\n\n\n\n<p>You want to&nbsp;<strong>maximize&nbsp;<\/strong><code>n<\/code><strong>&#8216;s numerical value<\/strong>&nbsp;by inserting&nbsp;<code>x<\/code>&nbsp;anywhere in the decimal representation of&nbsp;<code>n<\/code>\u200b\u200b\u200b\u200b\u200b\u200b. You&nbsp;<strong>cannot<\/strong>&nbsp;insert&nbsp;<code>x<\/code>&nbsp;to the left of the negative sign.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>For example, if&nbsp;<code>n = 73<\/code>&nbsp;and&nbsp;<code>x = 6<\/code>, it would be best to insert it between&nbsp;<code>7<\/code>&nbsp;and&nbsp;<code>3<\/code>, making&nbsp;<code>n = 763<\/code>.<\/li><li>If&nbsp;<code>n = -55<\/code>&nbsp;and&nbsp;<code>x = 2<\/code>, it would be best to insert it before the first&nbsp;<code>5<\/code>, making&nbsp;<code>n = -255<\/code>.<\/li><\/ul>\n\n\n\n<p>Return&nbsp;<em>a string representing the&nbsp;<strong>maximum<\/strong>&nbsp;value of&nbsp;<\/em><code>n<\/code><em>\u200b\u200b\u200b\u200b\u200b\u200b after the insertion<\/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> n = \"99\", x = 9\n<strong>Output:<\/strong> \"999\"\n<strong>Explanation:<\/strong> The result is the same regardless of where you insert 9.\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> n = \"-13\", x = 2\n<strong>Output:<\/strong> \"-123\"\n<strong>Explanation:<\/strong> You can make n one of {-213, -123, -132}, and the largest of those three is -123.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= n.length &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>1 &lt;= x &lt;= 9<\/code><\/li><li>The digits in&nbsp;<code>n<\/code>\u200b\u200b\u200b are in the range&nbsp;<code>[1, 9]<\/code>.<\/li><li><code>n<\/code>&nbsp;is a valid representation of an integer.<\/li><li>In the case of a negative&nbsp;<code>n<\/code>,\u200b\u200b\u200b\u200b\u200b\u200b it will begin with&nbsp;<code>'-'<\/code>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Greedy<\/strong><\/h2>\n\n\n\n<p>Find the best position to insert x. For positive numbers, insert x to the first position i such that s[i] &lt; x or s[i] > x for negatives.<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(1)<\/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  string maxValue(string n, int x) {\n    const int l = n.length();    \n    if (n[0] == '-') {\n      for (int i = 1; i <= l; ++i)\n        if (i == l || n[i] - '0' > x)\n          return n.substr(0, i) + static_cast<char>('0' + x) + n.substr(i);\n    } else {\n      for (int i = 0; i <= l; ++i)\n        if (i == l || x > n[i] - '0')\n          return n.substr(0, i) + static_cast<char>('0' + x) + n.substr(i);\n    }\n    return \"\";\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given a very large integer&nbsp;n, represented as a string,\u200b\u200b\u200b\u200b\u200b\u200b and an integer digit&nbsp;x. The digits in&nbsp;n&nbsp;and the digit&nbsp;x&nbsp;are in the&nbsp;inclusive&nbsp;range&nbsp;[1, 9], and&nbsp;n&nbsp;may represent&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[51],"tags":[88,177,4],"class_list":["post-8523","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-greedy","tag-medium","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8523","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=8523"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8523\/revisions"}],"predecessor-version":[{"id":8526,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8523\/revisions\/8526"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8523"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8523"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8523"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}