【刷题记录】11. 盛最多水的容器

一、题目描述

来源：力扣（LeetCode）

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

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

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

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]

输出：49

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

示例 2：

输入： height = [1,1]

输出： 1

提示：

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

二、思路分析

• 最直接的想法，确定左边的端点。移动右边端点。记录过程中的水容量，取得最大值.(见下面代码和运行然后GG)

代码

class Solution {

   public int maxArea(int[] height) {

       int len = height.length;

       int ans = 0;

       for (int i = 0; i < n; i++) {

           for (int j = i + 1; j < n; j++) {

               int w = j - i;

               int h = Math.min(height[i], height[j]);

               ans = Math.max(w * h, ans);

           }

       }

       return ans;

   }

}

复杂度分析

时间复杂度：

空间复杂度：

运行结果

然后就 超出时间限制了!!!

• 利用双指针

• 设两指针 i , j ，指的是容器高度分别为 h[i] , h[j] ，此状态下水容量为 S(i, j)
• 纳水的高度由两板中的 短板（即高度数字小） 决定, 水量为
  S(i,j)=min(h[i],h[j])×(j−i)
• 当我们移动左右端点的时候，无论移动左还是有 至今的宽度都是会-1
  所以考虑中间水的容量时候（考虑数字小的为高度）

• 若向内 移动数字小的端点 ，水槽的短板 min(h[i], h[j])可能变大，因此下个水的容量 可能增大
• 若向内 移动数字小的端点 ，水槽的短板 min(h[i], h[j]) 可能不变或变小，因此下个水容量 一定变小
• 所以我们移动端点的时候 就移动两端点中数字小的一边

• 初始化 两指针为最两边端点（即数组两端），然后逐步向内移动，直到两指针相遇，即结束。过程中最大的水容量就是最后我们需要的结果

三、代码实现

class Solution {
    public int maxArea(int[] height) {
        int l =0;
        int r = height.length -1;
        int res =0;
while (l < r) {
            //当前的水容量
            int tol = Math.min(height[l], height[r]) * (r - l);
            //更新结果 取最大
            res = Math.max(res, tol);
            // 判断那边端点移动
if (height[l] <= height[r]) {
++l;
            }
else {
--r;
            }
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：
  网络异常，图片无法展示

  |
  ，遍历数组一遍
• 空间复杂度：
  网络异常，图片无法展示

  |

运行结果

总结

在最通用的方法不满足我们的要求的时候，那就在这个基础上去想办法优化这个解法，来达到我们的需求。