关于java:LeetCode刷题笔记-11盛最多水的容器

2次阅读

共计 1148 个字符，预计需要花费 3 分钟才能阅读完成。

学好算法很重要，而后要学好算法，大量的练习是必不可少的，LeetCode 是我常常去的一个刷题网站，下面的题目十分具体，各个标签的题目都有，能够整体练习，本公众号后续会带大家做一做下面的算法题。

官网链接：https://leetcode-cn.com/probl…

难度：中等

https://leetcode-cn.com/probl…

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai)。在坐标内画 n 条垂直线，垂直线 i 的两个端点别离为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴独特形成的容器能够包容最多的水。

阐明：你不能歪斜容器。

示例

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

输出：height = [4,3,2,1,4]
输入：16

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

提醒：

n = height.length
2 <= n <= 3 * 104
0 <= height[i] <= 3 * 104

思路：

以容器左右边界，定义两个指针[left, right]。同时定义一个容器 count 用来寄存最大容量，以及一个变量 min 用来保留容器两边最短的线。

通过向内挪动两边界线较短的一方 (容器的容量取决于少的一方，超过该界线则水会溢出) 来扭转容器的容量，找出其中最大值。

代码：

class Solution {public int maxArea(int[] height) {
        // 定义变量
        int count = 0,left = 0, right = height.length - 1, min = 0;
        // 两端往两头挪动
        while(left < right){
            // 较短一方的线条长度
            min = Math.min(height[left], height[right]);
            // 更新最大面积
            count = Math.max(count, min * (right - left));
            // 挪动左边界
            while(left < right && height[left] <= min) {left++;}
            // 挪动右边界
            while(left < right && height[right] <= min) {right--;}
        }
        // 返回后果
        return count;
    }
}

复杂度剖析：