Java教程

LeetCode 11.盛最多水的容器【Java】

本文主要是介绍LeetCode 11.盛最多水的容器【Java】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录

  • 1.题目
  • 2.思路
  • 3.代码

1.题目

盛最多水的容器:

给你 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。

提示:

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

2.思路

看到这道题我最开始想到的还是直接两个for循环遍历得出最大值

public class Solution {
    public int maxArea(int[] height) {
        int ans = 0;
        for(int i = 0;i < height.length - 1;i ++){
            for(int j = height.length - 1;j > i;j --){
                int tmp = Math.min(height[i], height[j])*(j - i);
                ans = Math.max(tmp,ans);
            }
        }
        return ans;
    }
}

不出所料的超时了
O(N2)

看了下官方的题解(自己还是做不出来orz)
运用了双指针的思路:
1.
将数组的第一个元素和最后一个元素设为最初的两个指针
初始指针的位置
双指针指向数组的左右边界,数组的所有元素都可以成为指针。
那么我们要如何移动这两个边界来计算出最大的面积呢?

2.
从上面的图我们会想到先移动左侧的指针向右侧一步,也就是两个指针指向的值更小的那一侧去移动,我们才可能得到更大的面积值。
证明以上思路的过程如下:

假设我们去移动更大的一侧的指针:

设左右边界的指针指向的数分别为 I1 和 J1,设 I1 < J1, 数组元素个数为 n,所包围的面积为 S

∴ S1 = min(J1, I1) * n = I1 * n; //最初所包围的面积 

假设此时将右侧指针向左移动,指向的数为 j2 

if(J2 >= J1) 
	S2 = min(J2, I1) * (n - 1) = (I1 or J2) * (n - 1) < S1
else 
	S2 = min(J2, I1) * (n - 1) = I1 * (n - 1) < S1
	
由此可知无论如何移动右侧指针 S 的值都不会比 S1大。

剩下的就是当两个指针重合时, 得出的最大面积就是我们的答案
代码如下

3.代码

public class Solution {
    public int maxArea(int[] height) {
        int i = 0, j = height.length - 1;
        int max = 0;
        while (i != j) {
            int s = Math.min(height[j], height[i]) * (i - j);
            max = Math.max(max, s);
            if (height[j] <= height[i]) {
                j++;
            }
            else {
                i++;
            }
        }
        return max;
    }
}
小感悟:第一次这么认真的做了一道题,之前断断续续的做过几道题但都不太精,
这个文章也写的很差,图画的很难看,这篇文章和这道题就算是我leetcode的一个全新的开始吧,
今后每道题都会写这么一篇文章,尽量跟上卷王们的步伐(哭
这篇关于LeetCode 11.盛最多水的容器【Java】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!