长大后想做什么？做回小孩！

0%

LeetCode——盛最多水的容器

发表于 更新于 分类于 Valine：
本文字数： 386

NO.11 盛最多水的容器 中等

QfYcDK.png

思路一：暴力法 最简单的方法就是将所有的垂直线两两组合，每组计算出容纳的值，返回最大的值即可：

1
2
3
4
5
6
7
8
9
public int maxArea(int[] height) {
        int maxarea=0;
        for (int i=0;i<height.length;i++){
            for (int j=i+1;j<height.length;j++)
//                (j-i)一定要记得加括号。。。不要做蠢事
                maxarea=Math.max(maxarea,Math.min(height[i],height[j])*(j-i));
        }
        return maxarea;
    }

共有n(n-1)/2种组合，时间复杂度：O(n^2)

思路二：双指针法 用两个指针分别指向数组的开头和结尾，每次较短垂直线那端的指针向较长垂直线那端移动一个下标，每次移动之后用maxarea持续存储目前为止获得的最大面积，直到每个垂直线都被访问过一次为止。

套用语句说烂的话：一个木桶能盛多少水，取决于最短的那根木板。双指针法的形成思路和”短板效应“差不多，两根垂直线之间的面积取决于较短的那根垂直线m，所以想要得到更大的面积，较短的那根垂直线m必须要舍弃，因为如果不舍弃m，高最大就是m，而随着指针的移动宽一直在减少，因此面积只会越来越小：

1
2
3
4
5
6
7
8
9
10
11
12
public int maxArea(int[] height) {
    int maxarea=0,l=0,r=height.length-1;
    while (l<r){
        maxarea=Math.max(maxarea,Math.min(height[l],height[r])*(r-l));
        if (height[l]<height[r]){
            l++;
        }else {
            r--;
        }
    }
    return maxarea;
}

每个元素被访问一次，时间复杂度:O(n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github