{"id":2756,"date":"2025-03-16T20:58:40","date_gmt":"2025-03-16T12:58:40","guid":{"rendered":"https:\/\/guapicoding.com\/?p=2756"},"modified":"2025-07-26T14:18:50","modified_gmt":"2025-07-26T06:18:50","slug":"%e5%8a%9b%e6%89%a3%e9%a2%98%e8%ae%b0%e4%b9%8bhard","status":"publish","type":"post","link":"https:\/\/guapicoding.com\/?p=2756","title":{"rendered":"\u529b\u6263\u9898\u8bb0\u4e4bhard"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/vvXgSW\/\">LCR 078. \u5408\u5e76 K \u4e2a\u5347\u5e8f\u94fe\u8868<\/a><\/h2>\n\n\n\n<p><strong>\u65e2\u7136\u6bcf\u4e2a\u94fe\u8868\u90fd\u662f\u5347\u5e8f\u7684\uff0c\u90a3\u4e48\u5408\u5e76\u540e\u7684\u7b2c\u4e00\u4e2a\u8282\u70b9\u4e00\u5b9a\u662f\u67d0\u4e2a\u94fe\u8868\u7684\u5934\u8282\u70b9 <\/strong><\/p>\n\n\n\n<p><strong>\u5408\u5e76\u540e\u7684\u7b2c\u4e8c\u4e2a\u8282\u70b9\uff0c\u53ef\u80fd\u662f\u67d0\u4e2a\u94fe\u8868\u7684\u5934\u8282\u70b9\uff0c\u4e5f\u53ef\u80fd\u662f\u7b2c\u4e00\u4e2a\u8282\u70b9\u7684\u4e0b\u4e00\u4e2a\u8282\u70b9 <\/strong><\/p>\n\n\n\n<p><strong>\u6240\u4ee5\u6211\u4eec\u9700\u8981\u628a\u6240\u6709\u53ef\u80fd\u662f\u4e0b\u4e00\u4e2a\u8282\u70b9\u7684\u8282\u70b9\u653e\u5728\u4e00\u4e2a\u96c6\u5408\u4e2d\uff0c\u5e76\u4e14\u6700\u5c0f\u7684\u53ef\u4ee5\u81ea\u52a8\u6d6e\u8d77\u6765\uff0c\u5373<em>\u6700\u5c0f\u5806<\/em><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>\/**\n * Definition for singly-linked list.\n * struct ListNode {\n *     int val;\n *     ListNode *next;\n *     ListNode() : val(0), next(nullptr) {}\n *     ListNode(int x) : val(x), next(nullptr) {}\n *     ListNode(int x, ListNode *next) : val(x), next(next) {}\n * };\n *\/\nclass Solution {\npublic:\n    ListNode* mergeKLists(vector&lt;ListNode*&gt;&amp; lists) {\n        struct Comparator {  \n            bool operator()(ListNode *a, ListNode *b) {\n                return a-&gt;val &gt; b-&gt;val; \/\/\u4ee3\u8868\u5c0f\u6839\u5806\uff0c\u56e0\u4e3a\u5982\u679c\u8fd4\u56detrue\uff0c\u5c31\u8868\u793a\u5de6\u4fa7\u5143\u7d20\u7684\u4f18\u5148\u7ea7\u4f4e\u4e8e\u53f3\u4fa7\u5143\u7d20(\u6709\u70b9\u53cd\u76f4\u89c9)\n            }\n        };\n        priority_queue&lt;ListNode*, vector&lt;ListNode* &gt;, Comparator&gt; pq;\n        \/\/ \u5148\u628a\u6bcf\u4e2a\u94fe\u8868\u7684\u5934\u8282\u70b9\u90fd\u653e\u8fdb\u53bb\n        for(auto head : lists) {\n            if(head) pq.push(head);\n        }\n        ListNode* dummy = new ListNode();\n        ListNode* cur = dummy;\n        while(!pq.empty()) {\n            ListNode* node = pq.top(); \/\/ \u628a\u6700\u5c0f\u7684\u53d6\u51fa\u6765\n            pq.pop();\n            cur-&gt;next = node;\n            cur = cur-&gt;next;\n            if(node-&gt;next) pq.push(node-&gt;next);\n        }\n        return dummy-&gt;next;\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/first-missing-positive\/\">41. \u7f3a\u5931\u7684\u7b2c\u4e00\u4e2a\u6b63\u6570<\/a><\/h2>\n\n\n\n<p><strong><em>\u4e0d\u80fd\u6392\u5e8f\uff0c\u4e0d\u80fd\u5f00\u6570\u7ec4\uff0c\u53ea\u80fd\u7528\u6392\u6392\u961f\u7684\u601d\u8def\uff0c\u6bcf\u4e2a\u4eba\u90fd\u5fc5\u987b\u5750\u5728\u5c5e\u4e8e\u81ea\u5df1\u7684\u4f4d\u5b50\u4e0a<\/em><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    int firstMissingPositive(vector&lt;int&gt;&amp; nums) {\n        for(int i = 0; i &lt; nums.size(); i++) {\n            if(nums&#91;i] &lt; 0 || nums&#91;i] &gt; nums.size()) nums&#91;i] = 0;\n        }\n\n        for(int i = 0; i &lt; nums.size(); i++) {\n            if(nums&#91;i] &amp;&amp; nums&#91;i] != i + 1) { \/\/\u5982\u679c\u5750\u9519\u4e86\u4f4d\u7f6e\n                int tmp = nums&#91;i]; \/\/\u5750\u9519\u7684\u4eba\u5148\u7ad9\u4e00\u8fb9\u53bb \n                nums&#91;i] = 0; \/\/\u90a3\u4e48\u4f4d\u7f6e\u5c31\u7a7a\u4e86\n                while(tmp &gt; 0 &amp;&amp; nums&#91;tmp - 1] != tmp) { \/\/\u53bb\u627e\u5c5e\u4e8e\u81ea\u5df1\u7684\u4f4d\u7f6e tmp&gt;0\u4fdd\u8bc1\u7d22\u5f15\u5408\u6cd5\n                    if(!nums&#91;tmp - 1]) {\n                        nums&#91;tmp - 1] = tmp; \/\/\u6b63\u786e\u7684\u4f4d\u7f6e\u662f\u7a7a\u7684 \u76f4\u63a5\u5750\u4e0b\n                    } else { \/\/\u5df2\u7ecf\u6709\u4eba\u4e86\n                        int ta = nums&#91;tmp - 1]; \/\/\u8ba9\u4ed6\u79bb\u5f00\n                        nums&#91;tmp - 1] = tmp; \/\/tmp\u5750\u4e0b\n                        tmp = ta; \/\/ta\u53d8\u6210\u65b0\u7684tmp \u53bb\u627e\u6b63\u786e\u7684\u5ea7\u4f4d\n                    }\n                }\n            }\n        }\n        int i = 0;\n        for(i = 0; i &lt; nums.size() &amp;&amp; nums&#91;i]; i++);  \n        \/\/i\u53f7\u4f4d\u7f6e\u662f\u7a7a\u7684 \u8bf4\u660ei+1\u53f7\u4e58\u5ba2\u4e0d\u5728\n        \/\/\u5982\u679c\u6bcf\u4e2a\u4eba\u90fd\u5750\u5bf9\u4e86 \u90a3\u4e48\u8fd4\u56denums.size()+1 \u7b26\u5408\u9898\u610f\n        return i + 1;\n    }\n};<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/leetcode.cn\/problems\/number-of-visible-people-in-a-queue\/\">1944. \u961f\u5217\u4e2d\u53ef\u4ee5\u770b\u5230\u7684\u4eba\u6570<\/a><\/h2>\n\n\n\n<p><strong>\u5355\u8c03\u6808\uff1a\u4ece\u540e\u5f80\u524d\u904d\u5386\uff0c\u7ef4\u62a4\u4e00\u4e2a\u4ece\u6808\u5e95\u5230\u6808\u9876\u5355\u8c03\u9012\u51cf\u7684\u5e8f\u5217\uff0c\u5373\u7ef4\u62a4<strong>\u6ca1\u6709\u88ab\u6321\u4f4f<\/strong>\u7684\u4eba\u7684\u4f4d\u7f6e<\/strong>\u3002<\/p>\n\n\n\n<p>\u5982\u679c\u5de6\u8fb9\u7684\u80fd\u6321\u4f4f\u53f3\u8fb9\u7684\uff0c\u5c31\u5f39\u51fa\u53f3\u8fb9\uff0c\u56e0\u4e3a\u770b\u4e0d\u5230\u4ed6\u4e86\uff0c\u4fdd\u6301\u8eab\u9ad8\u5355\u8c03\u9012\u51cf\u3002<\/p>\n\n\n\n<p>\u82e5heights[i]\u5927\u4e8e\u6808\u9876\u5143\u7d20\uff0c\u5c31\u4e0d\u65ad\u5f39\u51fa\u5e76\u8ba1\u6570\uff08\u76f4\u5230\u6808\u9876\u5143\u7d20\u5927\u4e8eheights[i]\u6216\u8005\u6808\u7a7a\uff09\uff0c\u4f5c\u4e3a\u5b83\u80fd\u770b\u5230\u7684\u4eba\u6570\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class Solution {\npublic:\n    vector&lt;int> canSeePersonsCount(vector&lt;int>&amp; heights) {\n        stack&lt;int> sk; \/\/ \u7ef4\u62a4\u5355\u8c03\u9012\u51cf\u6808\n        vector&lt;int> res(heights.size(), 0);\n        for(int i = heights.size() - 1; i >= 0; i--) {\n            int cnt = 0;\n            while(!sk.empty() &amp;&amp; heights&#91;i] > heights&#91;sk.top()]) {\n                sk.pop(); \/\/ \u5982\u679c\u5de6\u8fb9\u7684\u80fd\u6321\u4f4f\u53f3\u8fb9\u7684 \u5c31\u5f39\u51fa\u53f3\u8fb9 \u56e0\u4e3a\u770b\u4e0d\u5230\u4ed6\u4e86\n                cnt++; \/\/ \u4e5f\u5c31\u662f\u8bf4 \u82e5heights&#91;i]\u5927\u4e8e\u6808\u9876\u5143\u7d20 \u5c31\u4e0d\u65ad\u5f39\u51fa\u5e76\u8ba1\u6570 \u4f5c\u4e3a\u5b83\u80fd\u770b\u5230\u7684\u4eba\u6570\n            }\n            if(!sk.empty()) cnt++;\n            sk.push(i);\n            res&#91;i] = cnt;\n        }\n        return res;\n    }\n};<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>LCR 078. \u5408\u5e76 K \u4e2a\u5347\u5e8f\u94fe\u8868 \u65e2\u7136\u6bcf\u4e2a\u94fe\u8868\u90fd\u662f\u5347\u5e8f\u7684\uff0c\u90a3\u4e48\u5408\u5e76\u540e\u7684\u7b2c\u4e00\u4e2a\u8282\u70b9\u4e00\u5b9a\u662f\u67d0\u4e2a\u94fe\u8868\u7684\u5934\u8282\u70b9  [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[27,18],"class_list":["post-2756","post","type-post","status-publish","format-standard","hentry","category-suanfa","tag-c","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/2756","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2756"}],"version-history":[{"count":4,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/2756\/revisions"}],"predecessor-version":[{"id":2808,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/2756\/revisions\/2808"}],"wp:attachment":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2756"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2756"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2756"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}