[Java·算法·中等]LeetCode11. 盛最多水的容器

朴灿烈づ我的快乐病毒、 2023-09-24 20:58 113阅读 0赞

#### 每天一题，防止痴呆 ####

*  题目
 *  示例
 *  分析思路1
 *  题解1
 *  分析思路2
 *  题解2

## 题目 ##

给定一个长度为 `n` 的整数数组 `height` 。有 `n` 条垂线，第 `i` 条线的两个端点是 `(i, 0)` 和 `(i, height[i])` 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

## 示例 ##

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

输入：[1,8,6,2,5,4,8,3,7]
    输出：49 
    解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

输入：height = [1,1]
    输出：1

## 分析思路1 ##

使用双指针法，在数组中从左右两端分别设立一个指针，并计算当前左右指针之间的面积，然后将面积与最大面积进行比较，更新最大面积。接着，将较小的指针向较大的指针方向移动一位，再进行面积计算，直到两个指针相遇。  
无论是移动短板或者长板，我们都只关注移动后的新短板会不会变长，而每次移动的木板都只有三种情况，比原短板短，比原短板长，与原短板相等；如向内移动长板，对于新的木板：1.比原短板短，则新短板更短。2.与原短板相等或者比原短板长，则新短板不变。所以，向内移动长板，一定不能使新短板变长。

## 题解1 ##

class Solution {
        
        public int maxArea(int[] height) {
        
            int maxArea = 0;
            int i = 0;
            int j = height.length-1;
    
            while (i<j){
        
                int currentArea = Math.min(height[i],height[j])*(j-i);
                maxArea = Math.max(maxArea, currentArea);
                if(height[i]<height[j]){
        
                    i++;
                }else {
        
                    j--;
                }
            }
            return maxArea;
        }
    }

执行结果  
![在这里插入图片描述][7b2e19230ebd41b8a11d5702c22e9d3e.png]

## 分析思路2 ##

仍然是双指针，但是写的简略一些，巧妙运用三元表达式。

## 题解2 ##

class Solution {
        
        public int maxArea(int[] height) {
        
            int i = 0, j = height.length - 1, res = 0;
            while(i < j) {
        
                res = height[i] < height[j] ? 
                    Math.max(res, (j - i) * height[i++]): 
                    Math.max(res, (j - i) * height[j--]); 
            }
            return res;
        }
    }

执行结果  
![在这里插入图片描述][1dfddd7d045243abaa89aad05fe0c053.png]

[6833fd42d923448c9dd3df5752248628.png]: https://img-blog.csdnimg.cn/6833fd42d923448c9dd3df5752248628.png
[7b2e19230ebd41b8a11d5702c22e9d3e.png]: https://img-blog.csdnimg.cn/7b2e19230ebd41b8a11d5702c22e9d3e.png
[1dfddd7d045243abaa89aad05fe0c053.png]: https://img-blog.csdnimg.cn/1dfddd7d045243abaa89aad05fe0c053.png