{"id":6100,"date":"2020-01-15T20:52:12","date_gmt":"2020-01-16T04:52:12","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6100"},"modified":"2020-01-15T21:53:03","modified_gmt":"2020-01-16T05:53:03","slug":"leetcode-42-trapping-rain-water","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-42-trapping-rain-water\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 42. Trapping Rain Water"},"content":{"rendered":"\n<p><a href=\"\"><\/a>Given&nbsp;<em>n<\/em>&nbsp;non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.<\/p>\n\n\n\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 42. Trapping Rain Water - \u5237\u9898\u627e\u5de5\u4f5c EP300\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/StH5vntauyQ?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2018\/10\/22\/rainwatertrap.png\" alt=\"\"\/><\/figure>\n\n\n\n<p><br>The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.&nbsp;<strong>Thanks Marcos<\/strong>&nbsp;for contributing this image!<\/p>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> [0,1,0,2,1,0,1,3,2,1,2,1]\n<strong>Output:<\/strong> 6<\/pre>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: Brute Force<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/42-ep300-1.png\" alt=\"\" class=\"wp-image-6108\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/42-ep300-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/42-ep300-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/42-ep300-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>r[i] = min(max(h[0:i+1]), max(h[i:n]))<br>ans = sum(r[i])<\/p>\n\n\n\n<p>Time complexity: O(n^2)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int trap(vector<int>& height) {\n    const int n = height.size();\n    int ans = 0;\n    auto sit = cbegin(height);\n    auto eit = cend(height);\n    for (int i = 0; i < n; ++i) {\n      int l = *max_element(sit, sit + i + 1);\n      int r = *max_element(sit + i, eit);\n      ans += min(l, r) - height[i];\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: DP<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/42-ep300-2.png\" alt=\"\" class=\"wp-image-6109\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/42-ep300-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/42-ep300-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/42-ep300-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>l[i] := max(h[0:i+1])<br>r[i] := max(h[i:n])<br>ans = sum(min(l[i], r[i]) - h[i])<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int trap(vector<int>& height) {\n    const int n = height.size();\n    vector<int> l(n);\n    vector<int> r(n);\n    int ans = 0;\n    for (int i = 0; i < n; ++i)\n      l[i] = i == 0 ? height[i] : max(l[i - 1], height[i]);\n    for (int i = n - 1; i >= 0; --i)\n      r[i] = i == n - 1 ? height[i] : max(r[i + 1], height[i]);\n    for (int i = 0; i < n; ++i)\n      ans += min(l[i], r[i]) - height[i];\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 3: Two Pointers<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/42-ep300-3.png\" alt=\"\" class=\"wp-image-6110\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/42-ep300-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/42-ep300-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/42-ep300-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua, 4 ms, 9.1 MB\nclass Solution {\npublic:\n  int trap(vector<int>& height) {\n    const int n = height.size();\n    if (n == 0) return 0;\n    int l = 0;\n    int r = n - 1;\n    int max_l = height[l];\n    int max_r = height[r];\n    int ans = 0;\n    while (l < r) {      \n      if (max_l < max_r) {\n        ans += max_l - height[l];\n        max_l = max(max_l, height[++l]);\n      } else {\n        ans += max_r - height[r];\n        max_r = max(max_r, height[--r]);\n      }\n    }\n    return ans;\n  }\n};\n\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given&nbsp;n&nbsp;non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[20,18,217,376,175],"class_list":["post-6100","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-array","tag-dp","tag-hard","tag-on","tag-two-pointers","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6100","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=6100"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6100\/revisions"}],"predecessor-version":[{"id":6111,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6100\/revisions\/6111"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6100"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6100"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6100"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}