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

算法升级之路（七）-盛最多水的容器

news 2025/8/28 8:43:07

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

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

返回容器可以储存的最大水量。
原题链接: 盛最多水的容器

解题思路：
这道题乍一看没什么思路，用暴力循环的话太麻烦了，要从第一个循环剩下的所有，第二个循环剩下的所有，第三个。。。
我也是看了答案之后才明白怎么算，其实很简单。

这个盛水的面积= min（height[i]，height[j]）*（j-i）；

从i=0 和j=heigh.length-1算起
在这个状态下只要挪动板子，（j-i）都是会变小

min（height[i]，height[j] 只有变大才有机会变大

由于求的是最小值，那么只有最小值变大，面积才有变大的可能。
所以每次挪动最小的板子，直到两个板子重合，就能得出最大面积。

代码

 public int maxArea(int[] height) {int area = 0;int front =0;int backend =height.length-1;while(front!=backend){int   current =Math.min(height[front],height[backend])*(backend-front);if(current>area){area = current;}if(height[front]<height[backend]){front++;}else{backend--;}}return area;}