当前位置：首页 > news >正文

【LeetCode】11. 盛水最多的容器题解

news 2026/6/2 5:27:34

【LeetCode】11. 盛水最多的容器题解

Link: https://leetcode.cn/problems/container-with-most-water/description/

给定一个长度为n nn的整数数组h hh（对应代码里的height）。有n nn条垂线，第i ii条线的两个端点是( i , 0 ) (i, 0)(i,0)和( i , h i ) (i, h_i)(i,hi)。

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

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

说明：不能倾斜容器。

输入输出样例

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

样例输入 2：( 1 , 1 ) (1,1)(1,1)
样例输出 2：1 11

数据规模与约定

2 ≤ n ≤ 10 5 2 \le n \le 10^52≤n≤105
∀ i ∈ { 1 , 2 , ⋯ , n } , 0 ≤ h i ≤ 10 4 \forall i \in \{1,2,\cdots, n\}, \quad 0\le h_i \le 10^4∀i∈{1,2,⋯,n},0≤hi≤104

Solution

Link: https://leetcode.cn/problems/container-with-most-water/solutions/3971886/11-sheng-shui-zui-duo-de-rong-qi-ti-jie-lx0x4/

1. 题意

已知一系列隔板的高度以及位置，求一对隔板使得其之间能够容纳最多体积的水。

2. 分析

比较入门的双指针板题。

首先，我们可以发现，能容纳水的体积等于两根线之间的水平距离乘以两根线高度的较小者（也就是有效高度）。

对于当前选定的一对下标（左右指针的位置）( l , r ) (l,r)(l,r)，其中必然一根线较长一根较短。

对于较长的线，如果将该处的指针（下标）往内移动，则依然会受制于短线的高度约束，中间可以容纳水的体积必然减小。这么做一定是更劣的。
对于较短的线，如果将该处的指针往内移动，则宽度减小的同时，有可能会遇到更长的线，从而使得有效高度增加，因此这种策略下有可能取得更优解。

照着这个思路就很容易写出代码了，时间复杂度O ( n ) O(n)O(n)，空间复杂度不计入参数列表则为O ( 1 ) O(1)O(1)。

若将参数列表计入，则全局的空间复杂度亦为O ( n ) O(n)O(n)。

3. 代码

publicclassSolution{publicintMaxArea(int[]height){intleft=0,right=height.Length-1,ans=-1;while(left<right){intcurrent=(right-left)*Math.Min(height[left],height[right]);ans=Math.Max(ans,current);if(height[left]<height[right]){left++;}else{right--;}}returnans;}}