【LeetCode Top 100】11. Container With Most Water【Medium】【JAVA】

男娘i 2021-09-21 00:16 148阅读 0赞

## 1. 题目 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]

## 2. 题意 ##

题目的意思是一个数组，数组的每个值代表一个柱子的高度，求所有柱子两两组合中，两个柱子跟x轴组成的区域最大容纳水的量。转换为数学关系就是所有垂直x轴的线段两两组合，每个组合的值为两个线段之间的距离与两条线段中较短线段的乘积。

## 3. 思路 ##

最容易的思路就是，将所有的情况进行遍历，即循环遍历每种情况，暴力法求解，时间复杂度为O(n²)。然后我们考虑如何降低时间复杂度，我们可以考虑，从柱子的最外面两侧的柱子，向中间进行靠拢，对于**外侧的柱子，他们已经取得了更大的两线段之间的距离**，为了获取更大的面积，**向内移动的过程中，需要不断更换组合中矮的柱子**，才有可能获得更大的面积。  
思路总结：通过设置两个“指针”，从最外面两侧的柱子向中间进行靠拢，每次移动的柱子为高度低的柱子，每次移动一格，移动后计算当前获取的面积跟当前最大面积值，若大于当前最大面积值而覆盖，之后再比较两个柱子的高度，重复比较-移动-计算的过程，直到两个柱子相遇。总体时间复杂度为O(n)。

## 4. 解题代码 ##

暴力法：

public int maxArea(int[] height) { 
            int maxArea = 0;
            // 遍历所有情况进行比较求解
            for (int i = 0; i < height.length; i++) { 
                for (int j = i + 1; j < height.length; j++) { 
                    int temp = (j - i) * minHeight(height[i], height[j]);
                    if (maxArea < temp) { 
                        maxArea = temp;
                    }
                }
            }
            return maxArea;
        }
    
        private int minHeight(int a, int b) { 
            return a > b ? b : a;
        }

从两侧向中间移动的方法：

public int maxArea(int[] height) { 
            int maxArea = 0, start = 0, end = height.length - 1;
            
            // 直到两个柱子相遇结束
            while (start < end) { 
            	// 判断当前组合是否取得更大面积
                int temp = (end - start) * minHeight(height[start], height[end]);
                if (temp > maxArea) { 
                    maxArea = temp;
                }
                
                // 判断应该移动的柱子
                if (height[start] < height[end]) { 
                    start++;
                } else { 
                    end--;
                }
            }
            return maxArea;
        }
    
        private int minHeight(int a, int b) { 
            return a > b ? b : a;
        }

## 5. 运行结果 ##

![在这里插入图片描述][20191207195951271.png]

## 6. 相关链接 ##

[本题代码的github链接][github]  
[其他 LeetCode 题目解析][LeetCode]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]: /images/20210920/fb66408e40d049189f76b29b1f5dcac8.png
[20191207195951271.png]: /images/20210920/f4aa0175232d41d2bd546960fe52aefe.png
[github]: https://github.com/Parallelline1996/Leetcode/blob/master/Problems/src/main/java/page1/N11_ContainerWithMostWater.java
[LeetCode]: https://blog.csdn.net/applying/category_9629399.html