{"id":871,"date":"2025-09-30T18:07:41","date_gmt":"2025-09-30T10:07:41","guid":{"rendered":"https:\/\/www.guanhaobo.cn\/?p=871"},"modified":"2025-09-30T18:08:16","modified_gmt":"2025-09-30T10:08:16","slug":"leetcode-42-%e6%8e%a5%e9%9b%a8%e6%b0%b4","status":"publish","type":"post","link":"https:\/\/www.guanhaobo.cn\/?p=871","title":{"rendered":"LeetCode 42 \u2013 \u63a5\u96e8\u6c34"},"content":{"rendered":"

\u9898\u76ee\u63cf\u8ff0<\/h1>\n

\u7ed9\u5b9a n \u4e2a\u975e\u8d1f\u6574\u6570\u8868\u793a\u6bcf\u4e2a\u5bbd\u5ea6\u4e3a 1 \u7684\u67f1\u5b50\u7684\u9ad8\u5ea6\u56fe\uff0c\u8ba1\u7b97\u6309\u6b64\u6392\u5217\u7684\u67f1\u5b50\uff0c\u4e0b\u96e8\u4e4b\u540e\u80fd\u63a5\u591a\u5c11\u96e8\u6c34\u3002<\/p>\n

\u793a\u4f8b 1\uff1a
\n\u8f93\u5165\uff1aheight = [0,1,0,2,1,0,1,3,2,1,2,1]
\n\u8f93\u51fa\uff1a6
\n\u89e3\u91ca\uff1a\u4e0a\u9762\u662f\u7531\u6570\u7ec4 [0,1,0,2,1,0,1,3,2,1,2,1] \u8868\u793a\u7684\u9ad8\u5ea6\u56fe\uff0c\u5728\u8fd9\u79cd\u60c5\u51b5\u4e0b\uff0c\u53ef\u4ee5\u63a5 6 \u4e2a\u5355\u4f4d\u7684\u96e8\u6c34\uff08\u84dd\u8272\u90e8\u5206\u8868\u793a\u96e8\u6c34\uff09\u3002<\/p>\n

\u9898\u76ee\u5206\u6790<\/h1>\n

\u52a8\u6001\u89c4\u5212<\/h2>\n

\u6bcf\u4e2a\u4f4d\u7f6e i \u80fd\u63a5\u5230\u591a\u5c11\u96e8\u6c34\uff0c\u53d6\u51b3\u4e8e\u5b83\u5de6\u8fb9\u7684\u6700\u9ad8\u70b9\u548c\u53f3\u8fb9\u7684\u6700\u9ad8\u70b9\uff0c\u53d6\u76f8\u5bf9\u8f83\u4f4e\u7684\u90a3\u4e2a\uff0c\u5047\u8bbe\u4e3a h\u3002h > height[i] \u65f6\uff0c\u80fd\u63a5\u5230\u6c34\u91cf\u4e3a h – height[i].
\n\u4f7f\u7528\u6570\u7ec4\u7ef4\u62a4\u6240\u6709\u5de6\u533a\u95f4\u7684\u6700\u9ad8\u70b9\u548c\u53f3\u533a\u95f4\u7684\u6700\u9ad8\u70b9\uff0c\u5c31\u53ef\u4ee5\u8fdb\u4e00\u6b65\u8ba1\u7b97\u6bcf\u4e2a\u4f4d\u7f6e\u80fd\u63a5\u5230\u7684\u6c34\u91cf\uff0c\u7d2f\u52a0\u5728\u4e00\u8d77\u5373\u53ef\u3002
\n\u65f6\u95f4\u590d\u6742\u5ea6 O(n)\uff0c\u7a7a\u95f4\u590d\u6742\u5ea6 O(n)<\/p>\n

\u53cc\u6307\u9488\uff08\u63a8\u8350\uff09<\/h2>\n

\u548c\u524d\u9762\u601d\u60f3\u4e00\u81f4\uff0c\u53ea\u662f\u628a\u4ece\u5de6\u5230\u53f3\u6309\u987a\u5e8f\u679a\u4e3e\uff0c\u53d8\u6210\u4ece\u4e24\u7aef\u5411\u5185\u679a\u4e3e\u6700\u9ad8\u70b9\u8f83\u5c0f\u7684\u90a3\u4e2a\u3002
\n\u4f7f\u7528\u53cc\u6307\u9488 l, r \u4ece\u4e24\u7aef\u7ef4\u62a4 [0, l] \u7684\u6700\u5927\u503c maxL \u548c [r, n-1] \u7684\u6700\u5927\u503c maxR.
\n\u4efb\u4e00\u65f6\u523b\uff0c\u5bf9\u4e8e maxL \u548c maxR \u4e2d\u8f83\u5c0f\u7684\u503c\u6240\u5728\u7684\u683c\u5b50\uff0c\u6700\u5927\u6c34\u4f4d\u5df2\u7ecf\u786e\u5b9a\uff0c\u5373 min(maxL, maxR)\uff0c\u8ba1\u7b97\u540e\u5c06\u88ab\u8ba1\u7b97\u7684\u6307\u9488\u4f4d\u7f6e\u5411\u5185\u79fb\u52a8\u4e00\u4f4d\u5373\u53ef
\n\u65f6\u95f4\u590d\u6742\u5ea6 O(n)\uff0c\u7a7a\u95f4\u590d\u6742\u5ea6 O(1)<\/p>\n

\u5355\u8c03\u6808<\/h2>\n

\u5355\u8c03\u6808\uff0c\u6808\u5185\u5b58\u50a8\u6570\u7ec4\u4e0b\u6807\u3002
\n\u4ece\u5de6\u5411\u53f3\u679a\u4e3e\u6570\u7ec4\uff0c\u9ad8\u5ea6\u5c0f\u4e8e\u7b49\u4e8e\u6808\u9876\u65f6\u5165\u6808\u3002\u679a\u4e3e\u9ad8\u5ea6\u5927\u4e8e\u6808\u9876\u65f6\uff0c\u8bf4\u660e\u5f53\u524d\u4f4d\u7f6e\u662f\u53f3\u8fb9\u754c\uff0c\u6808\u9876\u662f\u76f8\u5bf9\u5e95\u90e8\uff0c\u6b64\u65f6\u5c06\u6808\u9876\u51fa\u6808\uff0c\u65b0\u7684\u6808\u9876\u4e3a\u5de6\u8fb9\u754c\u3002
\n\u4e0d\u65ad\u5faa\u73af\u76f4\u5230\u6240\u6709\u5c0f\u4e8e\u5f53\u524d\u503c\u7684\u90fd\u51fa\u6808\uff0c\u6b64\u65f6\u65b0\u7684\u6808\u9876\u4ecd\u7136\u662f\u5de6\u8fb9\u754c\uff0c\u56e0\u6b64\u518d\u8ba1\u7b97\u4e00\u6b21\u5bb9\u91cf\u4f46\u65e0\u9700\u51fa\u6808\u3002\u6700\u540e\u628a\u5f53\u524d\u4f4d\u7f6e\u5165\u6808\uff0c\u7ee7\u7eed\u679a\u4e3e\u4e0b\u4e00\u4e2a\u4f4d\u7f6e\u3002
\n\u6bcf\u6b21\u53ea\u586b\u6ee1\u5f53\u524d\u80fd\u770b\u5230\u7684\u6a2a\u5411\u63a5\u6c34\u533a\u57df\uff0c\u7eb5\u5411\u5982\u679c\u8fd8\u5b58\u5728\u7a7a\u95f4\uff0c\u4f1a\u5728\u540e\u9762\u7684\u8ba1\u7b97\u4e2d\u8865\u5145\u4e0a\u3002
\n\u65f6\u95f4\u590d\u6742\u5ea6 O(n)\uff0c\u7a7a\u95f4\u590d\u6742\u5ea6 O(n)<\/p>\n

Java<\/h1>\n
public int trap1(int[] height) {\n    int sum = 0;\n    int size = height.length;\n    int[] leftHeight = new int[size];\n    leftHeight[0] = height[0];\n    for (int i = 1; i < size; i++) {\n        leftHeight[i] = Math.max(leftHeight[i - 1], height[i]);\n    }\n\n    int[] rightHeight = new int[size];\n    rightHeight[size - 1] = height[size - 1];\n    for (int i = size - 2; i >= 0; i--) {\n        rightHeight[i] = Math.max(rightHeight[i + 1], height[i]);\n    }\n\n    for (int i = 0; i < size; i++) {\n        int h = Math.min(leftHeight[i], rightHeight[i]);\n        if (h > height[i]) {\n            sum += h - height[i];\n        }\n    }\n    return sum;\n}\n\npublic int trap2(int[] height) {\n    int sum = 0;\n    int size = height.length;\n    int l = 0, r = size - 1;\n    int maxL = 0, maxR = 0;\n    while (l <= r) {\n        maxL = Math.max(height[l], maxL);\n        maxR = Math.max(height[r], maxR);\n        if (maxL <= maxR) {\n            sum += maxL - height[l];\n            l++;\n        } else {\n            sum += maxR - height[r];\n            r--;\n        }\n    }\n    return sum;\n}\n\npublic int trap3(int[] height) {\n    int sum = 0;\n    Deque<Integer> stack = new LinkedList<>();\n    stack.push(0);\n    for (int i = 1; i < height.length; i++) {\n        int curH = height[i];\n        while (!stack.isEmpty()) {\n            int top = stack.peek();\n            if (curH > height[top]) {\n                int r = i;\n                int bottom = stack.pop();\n                if (stack.isEmpty()) {\n                    break;\n                }\n                int l = stack.peek();\n                int h = Math.min(height[l], height[r]) - height[bottom];\n                int w = r - l - 1;\n                sum += h * w;\n            } else {\n                break;\n            }\n        }\n        stack.push(i);\n    }\n\n    return sum;\n}\n<\/code><\/pre>\n
Kotlin<\/h1>\n
fun trap(height: IntArray): Int {\n    var ans = 0\n    var l = 0\n    var r = height.size - 1\n    var maxL = 0\n    var maxR = 0\n\n    while (l <= r) {\n        maxL = maxL.coerceAtLeast(height[l])\n        maxR = maxR.coerceAtLeast(height[r])\n        if (maxL <= maxR) {\n            ans += maxL - height[l]\n            l++\n        } else {\n            ans += maxR - height[r]\n            r--\n        }\n    }\n    return ans\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9898\u76ee\u63cf\u8ff0 \u7ed9\u5b9a n \u4e2a\u975e\u8d1f\u6574\u6570\u8868\u793a\u6bcf\u4e2a\u5bbd\u5ea6\u4e3a 1 \u7684\u67f1\u5b50\u7684\u9ad8\u5ea6\u56fe\uff0c\u8ba1\u7b97\u6309\u6b64\u6392\u5217\u7684\u67f1\u5b50\uff0c\u4e0b\u96e8\u4e4b\u540e\u80fd\u63a5\u591a\u5c11\u96e8\u6c34\u3002  […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[20,40,76,75],"class_list":["post-871","post","type-post","status-publish","format-standard","hentry","category-algo","tag-leetcode","tag-40","tag-76","tag-75"],"_links":{"self":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/871","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=871"}],"version-history":[{"count":2,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/871\/revisions"}],"predecessor-version":[{"id":873,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/871\/revisions\/873"}],"wp:attachment":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=871"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=871"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=871"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}