{"id":2577,"date":"2018-06-06T20:55:08","date_gmt":"2018-06-06T12:55:08","guid":{"rendered":"https:\/\/nodelay.xyz\/?p=2577"},"modified":"2018-06-06T20:55:08","modified_gmt":"2018-06-06T12:55:08","slug":"leetcode-402-remove-k-digits","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=2577","title":{"rendered":"LeetCode 402. Remove K Digits"},"content":{"rendered":"<p>https:\/\/leetcode.com\/problems\/remove-k-digits\/description\/<br \/>\n\u5982\u679c\u76f4\u63a5\u7528DFS\u505a\u7684\u8bdd\u8f7b\u8f7b\u677e\u677e\u5c31\u4f1astack overflow\u3002<br \/>\n\u8fd9\u9053\u9898\u53ef\u4ee5\u7528\u8d2a\u5fc3\u6cd5\uff0c\u9898\u76ee\u6362\u4e2a\u601d\u8def\u8bf4\u5c31\u662f\u5c3d\u53ef\u80fd\u4fdd\u8bc1\u5f97\u5230\u7684\u6570\u5b57\u662f\u9012\u589e\u7684\u3002\u5728\u62ff\u5230\u4e00\u4e2a\u65b0\u6570\u5b57\u65f6\uff0c\u5c3d\u53ef\u80fd(\u53ea\u8981\u8fd8\u80fd\u5220)\u628a\u8be5\u6570\u5b57\u4e4b\u524d\u7684\u6bd4\u5b83\u5927\u7684\u6570\u5b57\u79fb\u6389\u3002<br \/>\n\u8d2a\u5fc3\u6cd5\u4e4b\u6240\u4ee5\u80fd\u7528\u662f\u56e0\u4e3a\u6211\u4eec\u53bb\u5c3d\u91cf\u4fdd\u8bc1\u4e86a1&lt;a2&lt; &#8230;&lt; x&lt; y\uff0c\u5982\u679c\u8fd9\u4e9b\u4e2a\u6570\u5b57\u91cc\u8981\u9009\u4e00\u4e2a\u5220\u6389\u7684\u8bdd\uff0c\u80af\u5b9a\u662f\u5220\u6389y\u5e26\u6765\u7684\u7ed3\u679c\u6700\u597d\u3002<\/p>\n<pre class=\"lang:c++ decode:true\">class Solution {\npublic:\n\tstring removeKdigits(string num, int k) {\n\t\tconst int digits = num.size() - k;\n        char* stack = new char[num.size()]; \/\/ mem leak but I DONT CARE!\n        int top = 0;\n        for (int i = 0; i &lt; num.size(); ++i)\n        {\n            char c = num[i];\n            while (top &gt; 0 &amp;&amp; stack[top-1] &gt; c &amp;&amp; k &gt; 0)\n            {\n                top--;\n                k--;\n            }\n            stack[top++] = c;\n        }\n        int idx = 0;\n        while (idx &lt; digits &amp;&amp; stack[idx] == '0')\n            idx++;\n        return idx == digits ? \"0\" : string(stack + idx, digits - idx);\n\t}\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/leetcode.com\/problems\/remove-k-digits\/description\/ \u5982\u679c\u76f4\u63a5\u7528DFS\u505a\u7684\u8bdd\u8f7b\u8f7b\u677e\u677e\u5c31\u4f1astack overflow\u3002 \u8fd9\u9053\u9898\u53ef\u4ee5\u7528\u8d2a\u5fc3\u6cd5\uff0c\u9898\u76ee\u6362\u4e2a\u601d\u8def\u8bf4\u5c31\u662f\u5c3d\u53ef\u80fd\u4fdd\u8bc1\u5f97\u5230\u7684\u6570\u5b57\u662f\u9012\u589e\u7684\u3002\u5728\u62ff\u5230\u4e00\u4e2a\u65b0\u6570\u5b57\u65f6\uff0c\u5c3d\u53ef\u80fd(\u53ea\u8981\u8fd8\u80fd\u5220)\u628a\u8be5\u6570\u5b57\u4e4b\u524d\u7684\u6bd4\u5b83\u5927\u7684\u6570\u5b57\u79fb\u6389\u3002 \u8d2a\u5fc3\u6cd5\u4e4b\u6240\u4ee5\u80fd\u7528\u662f\u56e0\u4e3a\u6211\u4eec\u53bb\u5c3d\u91cf\u4fdd\u8bc1\u4e86a1&lt;a2&lt; &#8230;&lt; x&lt; y\uff0c\u5982\u679c\u8fd9\u4e9b\u4e2a\u6570\u5b57\u91cc\u8981\u9009\u4e00\u4e2a\u5220\u6389\u7684\u8bdd\uff0c\u80af\u5b9a\u662f\u5220\u6389y\u5e26\u6765\u7684\u7ed3\u679c\u6700\u597d\u3002 class Solution { public: string removeKdigits(string num, int k) { const int digits = num.size() &#8211; k; char* stack = new char[num.size()]; \/\/ mem leak but I DONT CARE! int top = 0; for (int i = 0; i &lt; num.size(); ++i) { char c = num[i]; [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[49,66],"class_list":["post-2577","post","type-post","status-publish","format-standard","hentry","category-technical","tag-greedy-algo","tag-leetcode-oj"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2577","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2577"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2577\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2577"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2577"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2577"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}