{"id":1077,"date":"2017-12-03T01:00:38","date_gmt":"2017-12-03T09:00:38","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1077"},"modified":"2017-12-11T23:38:03","modified_gmt":"2017-12-12T07:38:03","slug":"leetcode-11-container-with-most-water","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/two-pointers\/leetcode-11-container-with-most-water\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 11. Container With Most Water"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 11. Container With Most Water - \u5237\u9898\u627e\u5de5\u4f5c EP121\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/IONgE6QZgGI?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><\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p>Given\u00a0<i>n<\/i>\u00a0non-negative integers\u00a0<i>a<sub>1<\/sub><\/i>,\u00a0<i>a<sub>2<\/sub><\/i>, &#8230;,\u00a0<i>a<sub>n<\/sub><\/i>, where each represents a point at coordinate (<i>i<\/i>,\u00a0<i>a<sub>i<\/sub><\/i>).\u00a0<i>n<\/i>\u00a0vertical lines are drawn such that the two endpoints of line\u00a0<i>i<\/i>\u00a0is at (<i>i<\/i>,\u00a0<i>a<sub>i<\/sub><\/i>) and (<i>i<\/i>, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.<\/p>\n<p>Note: You may not slant the container and\u00a0<i>n<\/i>\u00a0is at least 2.<\/p>\n<p><strong>Examples:<\/strong><\/p>\n<p>input: [1 3 2 4]<br \/>\noutput: 6<br \/>\nexplanation: use 3, 4, we have the following, which contains (4th-2nd) * min(3, 4) = 2 * 3 = 6 unit of water.<\/p>\n<pre class=\"\">   |\r\n|~~|\r\n|~~|\u00a0\r\n|~~|<\/pre>\n<p><strong>Idea:<\/strong><\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/11-ep121.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1087\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/11-ep121.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/11-ep121.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/11-ep121-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/11-ep121-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<p>Two pointers<\/p>\n<p>Time complexity: O(n)<\/p>\n<p>Space complexity: O(1)<\/p>\n<p><strong>Solution:<\/strong><\/p>\n<p>C++ two pointers<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Runtime: 19 ms\r\nclass Solution {\r\npublic:\r\n    int maxArea(const vector&lt;int&gt;&amp; height) {\r\n        int ans = 0;\r\n        int l = 0;\r\n        int r = height.size() - 1;\r\n        while (l &lt; r) {\r\n            int h = min(height[l], height[r]);\r\n            ans = max(ans, h * (r - l));\r\n            if (height[l] &lt; height[r]) \r\n                ++l;\r\n            else\r\n                --r;\r\n        }\r\n        return ans;\r\n    }\r\n};<\/pre>\n<p>Java<\/p>\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\r\n\/\/ Runtime: 13 ms\r\nclass Solution {\r\n    public int maxArea(int[] height) {\r\n        int l = 0;\r\n        int r = height.length - 1;\r\n        int ans = 0;\r\n        while (l &lt; r) {\r\n            int h = Math.min(height[l], height[r]);\r\n            ans = Math.max(ans, h * (r - l));\r\n            if (height[l] &lt; height[r])\r\n                ++l;\r\n            else\r\n                --r;\r\n        }\r\n        return ans;\r\n    }\r\n}<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem: Given\u00a0n\u00a0non-negative integers\u00a0a1,\u00a0a2, &#8230;,\u00a0an, where each represents a point at coordinate (i,\u00a0ai).\u00a0n\u00a0vertical lines are drawn such that the two endpoints of line\u00a0i\u00a0is at (i,\u00a0ai) and&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[176],"tags":[178,20,177,175],"class_list":["post-1077","post","type-post","status-publish","format-standard","hentry","category-two-pointers","tag-area","tag-array","tag-medium","tag-two-pointers","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1077","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=1077"}],"version-history":[{"count":10,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1077\/revisions"}],"predecessor-version":[{"id":1088,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1077\/revisions\/1088"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1077"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1077"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1077"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}