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

作者：WangNing

2022 年 7 月 15 日
本文字数：1204 字
阅读完需：约 4 分钟

一、题目描述

来源：力扣（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;    }}

复制代码

复杂度分析

时间复杂度： $O (n^{2})$

空间复杂度： $O (1)$

运行结果

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

利用双指针
设两指针 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;    }}

复制代码

复杂度分析

时间复杂度： $O (N)$ ，遍历数组一遍
空间复杂度： $O (1)$

运行结果

总结

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

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/1bed37b9cb0c8a00eef9e0a57】。

WangNing

关注

还未添加个人签名 2020.10.13 加入

一个只想提(快)升(乐)自(摸)我(鱼)的混子选手～

发布

暂无评论

创作场景

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

一、题目描述

二、思路分析

代码

复杂度分析

运行结果

三、代码实现

复杂度分析

运行结果

总结

WangNing

评论