{"id":1446,"date":"2025-06-15T15:58:00","date_gmt":"2025-06-15T07:58:00","guid":{"rendered":"http:\/\/114.55.108.251\/?p=1446"},"modified":"2025-07-26T14:18:52","modified_gmt":"2025-07-26T06:18:52","slug":"%e5%8a%9b%e6%89%a3%e9%a2%98%e8%ae%b0%e4%b9%8b%e6%a0%88","status":"publish","type":"post","link":"https:\/\/guapicoding.com\/?p=1446","title":{"rendered":"\u529b\u6263\u9898\u8bb0\u4e4b\u5355\u8c03\u6808"},"content":{"rendered":"\n

More content\uff1a<\/strong><\/em>LeetCode hot100@\u6808<\/a><\/p>\n\n\n\n

96. \u4e0b\u4e00\u4e2a\u66f4\u5927\u5143\u7d20 I<\/a>\u2705<\/h2>\n\n\n\n

\u5355\u8c03\u6808 + \u54c8\u5e0c<\/em><\/strong><\/p>\n\n\n\n

class Solution {\npublic:\n    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {\n        stack<int> sk; \/\/ \u5355\u8c03\u6808\u5b58\u4e0b\u6807\uff0c\u4fdd\u6301\u5bf9\u5e94\u5143\u7d20\u503c\u9012\u51cf\n        unordered_map<int, int> mp; \n        for(int i = 0; i < nums2.size(); i++) {\n            while(!sk.empty() && nums2[i] > nums2[sk.top()]) {\n                mp[nums2[sk.top()]] = nums2[i];\n                sk.pop();\n            }\n            sk.push(i);\n        }\n\n        vector<int> res(nums1.size(), -1);\n        for(int i = 0; i < nums1.size(); i++) {\n            if(mp.find(nums1[i]) != mp.end()) {\n                res[i] = mp[nums1[i]];\n            }\n        }\n\n        return res;\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
496. \u4e0b\u4e00\u4e2a\u66f4\u5927\u5143\u7d20 I<\/a>\u2705<\/h2>\n\n\n\n
\u5728\u4e0a\u4e00\u9898\u7684\u57fa\u7840\u4e0a \u5148\u6269\u5145\u4e00\u500d \u56e0\u4e3a\u603b\u80fd\u5728\u4e24\u6b21\u904d\u5386\u5185\u627e\u5230<\/strong><\/em> \u6700\u540e\u518d\u5c06\u7ed3\u679c\u7f29\u51cf\u4e00\u500d<\/strong><\/p>\n\n\n\n
class Solution {\npublic:\n    vector<int> nextGreaterElements(vector<int>& nums) {\n        stack<int> sk; \/\/ \u5355\u8c03\u6808\u5b58\u4e0b\u6807\uff0c\u4fdd\u6301\u5bf9\u5e94\u5143\u7d20\u503c\u9012\u51cf\n        vector<int> res(2 * nums.size(), -1);\n        vector<int> v(nums);\n        v.insert(v.end(), nums.begin(), nums.end()); \/\/ \u62fc\u63a5\u6570\u7ec4\n        for(int i = 0; i < v.size(); i++) {\n            while(!sk.empty() && v[i] > v[sk.top()]) {\n                res[sk.top()] = v[i];\n                sk.pop();\n            }\n            sk.push(i);\n        }\n        res.resize(nums.size());\n\n        return res;\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
402. \u79fb\u6389 K \u4f4d\u6570\u5b57<\/a>\u274c<\/h2>\n\n\n\n
\u6bd4\u8f83\u4e24\u4e2a\u6570\u5b57\u7684\u5927\u5c0f\uff0c\u662f\u4ece\u6700\u9ad8\u4f4d\u5f00\u59cb\u6bd4\u8f83\u7684\uff0c\u56e0\u6b64\u5c3d\u91cf\u4f7f\u6700\u9ad8\u4f4d\u53d8\u5c0f\uff0c\u4e5f\u5c31\u662f\u6539\u9020\u4f7f\u5f97\u6570\u5b57\u4ece\u9ad8\u4f4d\u5230\u4f4e\u4f4d\u9012\u589e\u3002<\/strong><\/em><\/p>\n\n\n\n
\u56e0\u6b64\u60f3\u5230\u7ef4\u62a4\u4e00\u4e2a\u9012\u589e\u5355\u8c03\u6808\u6765\u4fdd\u8bc1\u6700\u9ad8\u4f4d\u6700\u5c0f\uff0c\u5f53\u9047\u5230\u5c0f\u4e8e\u6808\u9876\u7684\u5143\u7d20\u65f6\uff0c\u5c31\u628a\u6808\u9876\u8fd9\u4e2a\u5927\u6570\u53bb\u6389\u3002<\/em><\/strong><\/p>\n\n\n\n
class Solution {\npublic:\n    string removeKdigits(string num, int k) {\n        stack<int> sk; \/\/ \u9012\u589e\u6808 \u5b58\u4e0b\u6807 \u4ee5\u6b64\u6765\u4fdd\u8bc1\u6700\u9ad8\u4f4d\u6700\u5c0f\n        for(int i = 0; i < num.size(); i++) {\n            while(!sk.empty() && num[i] < num[sk.top()] && k > 0) {     \n                sk.pop();\n                k--;\n            }\n            sk.push(i);\n        }\n        \n        while(!sk.empty() && k > 0) { \/\/ \u5982\u679c k \u8fd8\u6709\u4f59\u91cf\n            sk.pop();\n            k--;\n        }\n\n        \/\/ cout << \"---------------------\" << endl;\n        \/\/ stack<int> tmp = sk;\n        \/\/ while(!tmp.empty()) {\n        \/\/     cout << tmp.top() << \" \";\n        \/\/     tmp.pop();\n        \/\/ }\n        \/\/ cout << endl << \"---------------------\" << endl;\n\n        if(sk.empty()) return \"0\";\n        string res;\n        while(!sk.empty()) {\n            res += num[sk.top()];\n            sk.pop();\n        }\n        reverse(res.begin(), res.end());\n        \/\/ \u5904\u7406\u524d\u5bfc\u96f6\n        int p = 0;\n        int i = 0;\n        for(i = 0; i < res.size(); i++) {\n            if(res[i] == '0') p++;\n            else break;\n        }\n        if(i == res.size()) return \"0\"; \/\/ \u53ea\u6709\u96f6\u7684\u60c5\u51b5\n        return res.substr(i); \/\/ \u53ea\u586b\u7b2c\u4e00\u4e2a\u53c2\u6570\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
42. \u63a5\u96e8\u6c34<\/a>\u274c<\/h2>\n\n\n\n
Solution1\uff1a<\/strong><\/em>\u53cc\u6307\u9488 (\u6309\u5217\u8ba1\u7b97)<\/em><\/strong><\/p>\n\n\n\n
\u6bcf\u4e00\u5217\u96e8\u6c34\u7684\u9ad8\u5ea6\u53d6\u51b3\u4e8e\uff0c\u8be5\u5217\u5de6\u4fa7\u6700\u9ad8\u7684\u67f1\u5b50\u548c\u53f3\u4fa7\u6700\u9ad8\u7684\u67f1\u5b50\u4e2d\u8f83\u77ee\u7684\u90a3\u4e2a\u67f1\u5b50\u7684\u9ad8\u5ea6 – \u81ea\u8eab\u9ad8\u5ea6<\/em><\/strong><\/p>\n\n\n\n
Solution2\uff1a\u5355\u8c03\u6808<\/strong><\/em> (\u6309\u884c\u8ba1\u7b97)<\/strong><\/em><\/p>\n\n\n\n
\u6808\u5e95\u5230\u6808\u5934\u5143\u7d20\u9012\u51cf\uff0c\u56e0\u4e3a\u4e00\u65e6\u8981\u6dfb\u52a0\u7684\u67f1\u5b50\u9ad8\u5ea6\u5927\u4e8e\u6808\u5934\u5143\u7d20\uff0c\u8bf4\u660e\u51fa\u73b0\u51f9\u69fd\u4e86<\/em><\/strong><\/p>\n\n\n\n
\u6b64\u65f6\uff0c\u6808\u5934\u5143\u7d20\u5c31\u662f\u51f9\u69fd\u5e95\u90e8\u7684\u67f1\u5b50\uff0c\u6808\u5934\u7b2c\u4e8c\u4e2a\u5143\u7d20\u5c31\u662f\u51f9\u69fd\u5de6\u8fb9\u7684\u67f1\u5b50\uff0c\u800c\u6dfb\u52a0\u7684\u5143\u7d20\u5c31\u662f\u51f9\u69fd\u53f3\u8fb9\u7684\u67f1\u5b50 <\/strong><\/em><\/p>\n\n\n\n
class Solution1 {\npublic:\n    int trap(vector<int>& height) {\n        int res = 0;\n        int len = height.size();\n        \/\/\u8bb0\u5f55\u5f53\u524d\u5217\u7684\u5de6\u53f3\u4e24\u8fb9\u7684\u6700\u9ad8\u5217\n        vector<int> lmax(len);\n        vector<int> rmax(len);\n        \n        lmax[0] = height[0];\n        for(int i = 1; i < len; i++) {\n            lmax[i] = max(lmax[i-1], height[i]);\n        }\n\n        rmax[len - 1] = height[len - 1];\n        for(int i = len - 2; i >= 0; i--) {\n            rmax[i] = max(rmax[i+1], height[i]);\n        }\n\n        for(int i = 0; i < height.size(); i++) {\n            int x = min(lmax[i], rmax[i]) - height[i]; \/\/\u7b2c\u4e00\u5217\u548c\u6700\u540e\u4e00\u5217\u7684x\u7b97\u51fa\u6765\u662f0           \n            if(x > 0) res += x; \/\/\u662f\u6b63\u6570\u624d\u8bf4\u660e\u80fd\u63a5\u4f4f\u96e8\u6c34\uff0c\u8d1f\u6570\u7684\u60c5\u51b5\u6bd4\u5982\u6700\u9ad8\u5217\n        }\n\n        return res;\n    }\n};<\/code><\/pre>\n\n\n\n
class Solution2 {\npublic:\n    int trap(vector<int>& height) {\n        stack<int> sk; \/\/\u5b58\u4e0b\u6807\n        int res = 0;\n        sk.push(0);\n\n        for(int i = 1; i < height.size(); i++) {\n            while(!sk.empty() && height[i] > height[sk.top()]) { \/\/\u51fa\u73b0\u51f9\u69fd\n                int mid = height[sk.top()]; \/\/\u51f9\u69fd\u4e2d\u95f4\u67f1\u5b50\u9ad8\u5ea6\n                sk.pop();\n                if(!sk.empty()) {\n                    int left = height[sk.top()]; \/\/\u51f9\u69fd\u5de6\u8fb9\u67f1\u5b50\u9ad8\u5ea6\n                    int right = height[i]; \/\/\u51f9\u69fd\u53f3\u8fb9\u67f1\u5b50\u9ad8\u5ea6\n                    int h = min(left, right) - mid;\n                    int w = i - sk.top() - 1;\n                    res += h * w; \/\/\u9ad8\u00d7\u5bbd\n                }\n            }\n            sk.push(i);\n        }\n\n        return res;\n    }\n};<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
More content\uff1aLeetCode hot100@\u6808 96. \u4e0b\u4e00\u4e2a\u66f4\u5927\u5143\u7d20 I\u2705 \u5355\u8c03\u6808 + \u54c8\u5e0c  […]<\/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":[18,19,52],"class_list":["post-1446","post","type-post","status-publish","format-standard","hentry","category-suanfa","tag-leetcode","tag-19","tag-52"],"_links":{"self":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/1446","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=1446"}],"version-history":[{"count":14,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/1446\/revisions"}],"predecessor-version":[{"id":3402,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/1446\/revisions\/3402"}],"wp:attachment":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1446"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1446"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1446"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}