{"id":7379,"date":"2026-07-21T00:42:31","date_gmt":"2026-07-20T16:42:31","guid":{"rendered":"https:\/\/i007.cc\/wordpress\/?p=7379"},"modified":"2026-07-21T00:42:31","modified_gmt":"2026-07-20T16:42:31","slug":"%e6%8e%a5%e9%9b%a8%e6%b0%b4%ef%bc%88trapping-rain-water%ef%bc%89","status":"publish","type":"post","link":"https:\/\/i007.cc\/wordpress\/archives\/7379","title":{"rendered":"\u63a5\u96e8\u6c34\uff08Trapping Rain Water\uff09"},"content":{"rendered":"
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n

\u8fd9\u662f\u529b\u6263\u7b2c 42 \u9898\uff0c\u7ecf\u5178\u4e2d\u7684\u7ecf\u5178\u3002\u5148\u660e\u786e\u95ee\u9898\uff1a\u7ed9\u5b9a\u4e00\u4e2a\u6570\u7ec4\u8868\u793a\u67f1\u5b50\u9ad8\u5ea6\uff0c\u8ba1\u7b97\u80fd\u63a5\u591a\u5c11\u96e8\u6c34\u3002<\/p>\n

\n

\u6838\u5fc3\u601d\u8def\uff1a\u6bcf\u6839\u67f1\u5b50\u80fd\u63a5\u591a\u5c11\u6c34\uff1f<\/h4>\n

\u5bf9\u4e8e\u4f4d\u7f6e i<\/code>\uff0c\u5b83\u80fd\u63a5\u7684\u6c34\u91cf\u53d6\u51b3\u4e8e\uff1a<\/p>\n

\n

\u5b83\u5de6\u8fb9\u6700\u9ad8\u67f1\u5b50 \u548c \u53f3\u8fb9\u6700\u9ad8\u67f1\u5b50 \u4e2d\uff0c\u8f83\u77ee\u7684\u90a3\u4e2a<\/strong>\uff0c\u51cf\u53bb\u81ea\u8eab\u9ad8\u5ea6\u3002<\/p>\n<\/blockquote>\n

\n
\n
<\/div>\n<\/div>\n
\n
water[i] = max(0, min(leftMax[i], rightMax[i]) - height[i])<\/code><\/pre>\n<\/div>\n<\/div>\n
\u8fd9\u662f\u6240\u6709\u89e3\u6cd5\u7684\u5171\u540c\u672c\u8d28\uff0c\u533a\u522b\u53ea\u5728\u4e8e\u600e\u4e48\u6c42 leftMax<\/code> \u548c rightMax<\/code>\u3002<\/p>\n
\n
\u89e3\u6cd5\u4e00\uff1a\u9884\u5904\u7406\u6570\u7ec4\uff08\u7a7a\u95f4 O(n)\uff0c\u65f6\u95f4 O(n)\uff09<\/h4>\n
\u5148\u5206\u522b\u7b97\u597d\u6bcf\u4e2a\u4f4d\u7f6e\u7684\u5de6\u6700\u5927\u548c\u53f3\u6700\u5927\uff0c\u518d\u904d\u5386\u4e00\u904d\u6c42\u548c\u3002<\/p>\n
\n
\n
<\/div>\n<\/div>\n
python<\/div>\n
\n
def<\/span> trap<\/span>(<\/span>height)<\/span>:<\/span>\r\n    n =<\/span> len<\/span>(<\/span>height)<\/span>\r\n    left_max =<\/span> [<\/span>0<\/span>]<\/span> *<\/span> n\r\n    right_max =<\/span> [<\/span>0<\/span>]<\/span> *<\/span> n\r\n    \r\n    left_max[<\/span>0<\/span>]<\/span> =<\/span> height[<\/span>0<\/span>]<\/span>\r\n    for<\/span> i in<\/span> range<\/span>(<\/span>1<\/span>,<\/span> n)<\/span>:<\/span>\r\n        left_max[<\/span>i]<\/span> =<\/span> max<\/span>(<\/span>left_max[<\/span>i-<\/span>1<\/span>]<\/span>,<\/span> height[<\/span>i]<\/span>)<\/span>\r\n    \r\n    right_max[<\/span>n-<\/span>1<\/span>]<\/span> =<\/span> height[<\/span>n-<\/span>1<\/span>]<\/span>\r\n    for<\/span> i in<\/span> range<\/span>(<\/span>n-<\/span>2<\/span>,<\/span> -<\/span>1<\/span>,<\/span> -<\/span>1<\/span>)<\/span>:<\/span>\r\n        right_max[<\/span>i]<\/span> =<\/span> max<\/span>(<\/span>right_max[<\/span>i+<\/span>1<\/span>]<\/span>,<\/span> height[<\/span>i]<\/span>)<\/span>\r\n    \r\n    return<\/span> sum<\/span>(<\/span>min<\/span>(<\/span>left_max[<\/span>i]<\/span>,<\/span> right_max[<\/span>i]<\/span>)<\/span> -<\/span> height[<\/span>i]<\/span> for<\/span> i in<\/span> range<\/span>(<\/span>n)<\/span>)<\/span><\/code><\/pre>\n<\/div>\n<\/div>\n
\u601d\u8def\u6e05\u6670\uff0c\u4f46\u7528\u4e86\u989d\u5916\u7a7a\u95f4\u3002<\/p>\n
\n
\u89e3\u6cd5\u4e8c\uff1a\u53cc\u6307\u9488\uff08\u7a7a\u95f4 O(1)\uff0c\u65f6\u95f4 O(n)\uff09\u2b50 \u6700\u4f18<\/h4>\n
\u4e0d\u9884\u5904\u7406\u6570\u7ec4\uff0c\u7528\u53cc\u6307\u9488\u4ece\u4e24\u7aef\u5411\u4e2d\u95f4\u6536\u7f29\uff0c\u8fb9\u8d70\u8fb9\u7ef4\u62a4\u5de6\u53f3\u6700\u5927\u503c<\/strong>\u3002<\/p>\n
\n
\n
<\/div>\n<\/div>\n
python<\/div>\n
\n
def<\/span> trap<\/span>(<\/span>height)<\/span>:<\/span>\r\n    left,<\/span> right =<\/span> 0<\/span>,<\/span> len<\/span>(<\/span>height)<\/span> -<\/span> 1<\/span>\r\n    left_max =<\/span> right_max =<\/span> 0<\/span>\r\n    ans =<\/span> 0<\/span>\r\n    \r\n    while<\/span> left <<\/span> right:<\/span>\r\n        if<\/span> height[<\/span>left]<\/span> <<\/span> height[<\/span>right]<\/span>:<\/span>\r\n            if<\/span> height[<\/span>left]<\/span> >=<\/span> left_max:<\/span>\r\n                left_max =<\/span> height[<\/span>left]<\/span>\r\n            else<\/span>:<\/span>\r\n                ans +=<\/span> left_max -<\/span> height[<\/span>left]<\/span>\r\n            left +=<\/span> 1<\/span>\r\n        else<\/span>:<\/span>\r\n            if<\/span> height[<\/span>right]<\/span> >=<\/span> right_max:<\/span>\r\n                right_max =<\/span> height[<\/span>right]<\/span>\r\n            else<\/span>:<\/span>\r\n                ans +=<\/span> right_max -<\/span> height[<\/span>right]<\/span>\r\n            right -=<\/span> 1<\/span>\r\n    \r\n    return<\/span> ans<\/code><\/pre>\n<\/div>\n<\/div>\n
\u4e3a\u4ec0\u4e48\u8fd9\u6837\u662f\u5bf9\u7684\uff1f<\/strong> \u5173\u952e\u5728\u4e8e\uff1a<\/p>\n
\u5f53 height[left] < height[right]<\/code> \u65f6\uff0c\u5de6\u8fb9\u8f83\u77ee\uff0c\u51b3\u5b9a\u5de6\u4fa7\u79ef\u6c34\u7684\u74f6\u9888\u662f left_max<\/code>\uff0c\u4e0d\u9700\u8981\u7ba1\u53f3\u8fb9\u5230\u5e95\u6709\u591a\u9ad8\uff08\u53cd\u6b63\u53f3\u8fb9\u4e00\u5b9a \u2265 \u5f53\u524d height[right]<\/code> > height[left]<\/code>\uff09\u2014\u2014\u53f3\u8fb9\u5df2\u7ecf\u591f\u9ad8\u4e86\uff0c\u5de6\u8fb9\u80fd\u63a5\u591a\u5c11\u6c34\u53ea\u7531 left_max<\/code> \u51b3\u5b9a\uff0c\u6240\u4ee5\u53ef\u4ee5\u653e\u5fc3\u7ed3\u7b97\u5de6\u4fa7\u3002<\/p>\n
\n
\u89e3\u6cd5\u4e09\uff1a\u5355\u8c03\u6808\uff08\u53e6\u4e00\u79cd\u601d\u8def\uff09<\/h4>\n
\u6309\u6a2a\u5411<\/strong>\u8ba1\u7b97\u6bcf\u5c42\u7684\u6c34\uff0c\u7528\u6808\u7ef4\u62a4\u4e00\u4e2a\u5355\u8c03\u9012\u51cf\u5e8f\u5217\uff0c\u9047\u5230\u6bd4\u6808\u9876\u9ad8\u7684\u67f1\u5b50\u65f6\uff0c\u5f39\u51fa\u7ed3\u7b97\u3002\u4ee3\u7801\u7a0d\u590d\u6742\uff0c\u65f6\u95f4\u548c\u7a7a\u95f4\u5747 O(n)\uff0c\u4e0d\u5982\u53cc\u6307\u9488\u4f18\u96c5\uff0c\u4f46\u7406\u89e3\u5b83\u6709\u52a9\u4e8e\u5904\u7406\u7c7b\u4f3c\u7684”\u67f1\u72b6\u56fe”\u7cfb\u5217\u9898\u3002<\/p>\n
\n
\u4e09\u79cd\u89e3\u6cd5\u5bf9\u6bd4<\/h4>\n
\n\n\n\n\n\n\n\n
\u89e3\u6cd5<\/th>\n\u65f6\u95f4<\/th>\n\u7a7a\u95f4<\/th>\n\u63a8\u8350\u6307\u6570<\/th>\n<\/tr>\n<\/thead>\n
\u9884\u5904\u7406\u6570\u7ec4<\/td>\nO(n)<\/td>\nO(n)<\/td>\n\u2605\u2605\u2605\u2605 \u5165\u95e8\u9996\u9009<\/td>\n<\/tr>\n
\u53cc\u6307\u9488<\/strong><\/td>\nO(n)<\/strong><\/td>\nO(1)<\/strong><\/td>\n\u2605\u2605\u2605\u2605\u2605 \u9762\u8bd5\u6700\u4f18<\/strong><\/td>\n<\/tr>\n
\u5355\u8c03\u6808<\/td>\nO(n)<\/td>\nO(n)<\/td>\n\u2605\u2605\u2605 \u62d3\u5c55\u601d\u7ef4<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
\n
\u9762\u8bd5\u5efa\u8bae<\/h4>\n
\u5148\u8bb2”\u6bcf\u4e2a\u4f4d\u7f6e\u80fd\u63a5\u591a\u5c11\u6c34 = min(\u5de6\u6700\u5927, \u53f3\u6700\u5927) - \u81ea\u8eab\u9ad8\u5ea6<\/code>“\u5efa\u7acb\u76f4\u89c9\uff0c\u7136\u540e\u76f4\u63a5\u7ed9\u51fa\u53cc\u6307\u9488\u89e3\u6cd5\uff0c\u5e76\u89e3\u91ca\u4e3a\u4ec0\u4e48\u80fd\u7701\u6389\u9884\u5904\u7406\u6570\u7ec4\u2014\u2014\u8fd9\u4e2a\u63a8\u7406\u8fc7\u7a0b\u6700\u80fd\u4f53\u73b0\u7406\u89e3\u6df1\u5ea6\u3002<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n
<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
\u8fd9\u662f\u529b\u6263\u7b2c 42 \u9898\uff0c\u7ecf\u5178\u4e2d\u7684\u7ecf\u5178\u3002\u5148\u660e<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"colormag_page_container_layout":"default_layout","colormag_page_sidebar_layout":"default_layout","footnotes":""},"categories":[24],"tags":[],"class_list":["post-7379","post","type-post","status-publish","format-standard","hentry","category-value_docs"],"_links":{"self":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/7379","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/comments?post=7379"}],"version-history":[{"count":1,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/7379\/revisions"}],"predecessor-version":[{"id":7380,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/7379\/revisions\/7380"}],"wp:attachment":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/media?parent=7379"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/categories?post=7379"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/tags?post=7379"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}