[LeetCode 笔记] 11. Container With Most Water

前言

　　这题是一个运用双指标的算法，目标是找到可装最多水的容器 (面积)，只需一个 while 迴圈就可依依遍历到最大的面积答案，时间複杂度可估 O(n)，这里有 JAVA 和 Python 的写法。

题目

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.

给定一个长度为 n 的整数阵列 height ，画了 n 条的垂直线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])
找到两条线与方向 x 轴一起形成的容器，使得这个容器包含最多的水
回传可装最大容量的水的容器
注意 你不行倾斜容器

题目连结：https://leetcode.com/problems/container-with-most-water/

题目限制

n == height.length
2 <= n <= 105
0 <= height[i] <= 104

範例

Input: height = [1,8,6,2,5,4,8,3,7]Output: 49Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Input: height = [1,1]Output: 1

思路&笔记

这题题目要我们做的是，在一个阵列里取出两个元素后，找出两个元素相乘后的最大面积，使用的是双指标算法。

我们思考一下，算出容器的面积会需要的是高度和宽度设定高度，取用于阵列里各个元素的值另一方面制定两个指标，分别为 left 和 right，是要来代表容器的宽度并将 left = 0 作为宽度的起始点 (指标一)另外把 right = height.length - 1 作为宽度的结束点 (指标二)然后运用 while 遍历阵列，来找出最大的容器如果 left 比 right 矮的时候，代表需要找到下一个比较高的容器高度，要 left++如果 right 比 left 矮的时候，代表需要找到前一个比较高的容器高度，要 left--如果 right 等于 left 的时候，代表前后一起作用把容器缩小，要 right++ 和 left--

[补充] 从矮墙开始取得，是因为装水的时候基準会落在矮墙，超过矮墙的话水会溢出来，思考一下如果一个容器一边高一边低，水最多可以装到哪? 当然最多只能装到矮墙的最顶端，高墙就并不太重要了，取决于还是矮墙。

简易示意图

下述循环只演示到第三次，后续动作都是一样的逻辑

8          |                             |7          |                             |           |6          |     |                       |           |5          |     |           |           |           |4          |     |           |     |     |           |3          |     |           |     |     |     |     |2          |     |     |     |     |     |     |     |1    |     |     |     |     |     |     |     |     |     0     1     2     3     4     5     6     7     8    left                                           rightw = 8h = 1area = 8 * 1 = 8max = 0 更新为 8left < right，left++

8          |                             |7          |                             |           |6          |     |                       |           |5          |     |           |           |           |4          |     |           |     |     |           |3          |     |           |     |     |     |     |2          |     |     |     |     |     |     |     |1    |     |     |     |     |     |     |     |     |     0     1     2     3     4     5     6     7     8          left                                     rightw = 7h = 7area = 7 * 7 = 49max = 8 更新为 49left < right，right--

8          |                             |7          |                             |           |6          |     |                       |           |5          |     |           |           |           |4          |     |           |     |     |           |3          |     |           |     |     |     |     |2          |     |     |     |     |     |     |     |1    |     |     |     |     |     |     |     |     |     0     1     2     3     4     5     6     7     8          left                               rightw = 6h = 3area = 6 * 3 = 18max 不变，一样是 49left > right，left++

JAVA 实现

最简单的是暴力解，就是把一个一个的面积遍历出来比较，不过想当然儿送出结果跳出 Time Limit Exceeded 超过时间複杂度限制。

class Solution {    public int maxArea(int[] height) {        int max = 0; // 最大面积                for (int i=0; i<height.length; i++){            for (int j=i+1; j<height.length; j++){                int erea = (j-i) * Math.min(height[i], height[j]); // 宽度 * 最小高度                if (erea>max){                    max = erea; // 设定最大面积                }            }        }        return max;    }}

比较聪明的算法

class Solution {    public int maxArea(int[] height) {        int left = 0; // 指标一        int right = height.length - 1; // 指标二        int max = 0; // 最大的面积        while(left < right){            int w = right - left; // 算出宽度            int h = Math.min(height[left], height[right]); // 算出高度 (从最矮的开始)            int area = h * w; // 算出面积            max = Math.max(max, area); // 存入最大的面积            if(height[left] < height[right]) {left++; // 找下一个比较大的元素            }else if(height[left] > height[right]) {right--; // 找前一个比较大的元素            }else {                // 前后一起缩小                left++;                right--;            }        }        return max;    }}

Python 实现

使用了和 Java 一样的逻辑执行，换成 Python 的写法。

class Solution:    def maxArea(self, height: List[int]) -> int:        left = 0 # 指标一        right = len(height) - 1 # 指标二        max_area = 0 # 最大的面积        while left < right:            w = right - left # 算出宽度            h = min(height[left], height[right]) # 算出高度 (从最矮的开始)            area = w * h # 算出面积            max_area = max(max_area, area) # 存入最大的面积            if height[left] < height[right]:                left += 1 # 找下一个比较大的元素            elif height[left] > height[right]:                right -= 1 # 找前一个比较大的元素            else:                # 前后一起缩小                left += 1                right -= 1        return max_area

成绩

(新手上路，如有错误请友善告知，感谢)

Blog
https://chris81051.github.io/2023/06/26/LeetCode-11-Container-With-Most-Water-Java-Python/
有分享技术文章、科技新闻、日常生活，欢迎一起讨论