您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

20210407力扣11题:11. 盛最多水的容器JAVA

1.题目描述

给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/container-with-most-water

在这里插入图片描述

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

2.自己想法

起初 就想到用暴力破解的方法,用for循环,一个循环第一个数,一个循环下一个数,当temp大于面积时,进行交换值,最后返回面积即可。
代码:

class Solution {
    public int maxArea(int[] height) {
        int area = 0;//面积
        int temp = 0;//临时面积
        for(int i = 0;i<height.length;i++)
        {
            for(int j = i+1;j<height.length;j++)
            {
                if(height[i]<height[j])
                {
                    temp = height[i]*(j-i);
                }
                else
                {
                     temp = height[j] * (j-i);
                }
                if(temp > area) area = temp;
            }
        }
        return area;
    }
}

这样算是完成,提交的时候测试案例用了很多数,所以超时,两个for循环实在行不通。
那么就需要换个方法来做了,自己当时还在想用Arrays.sort()方法排序,找到最大的两个值,在找到最大值对应 的下标,计算temp面积,进行交换等,但是这样做了后发现还是存在问题。因为找到最大值相当于只考虑了宽度,没有考虑长度。
随后,查看了答案。

3.别人思路

官方给出了双指针的思路,让我拓宽了想法,是从两边向中间找最大面积,这样的循环也只需要进行一次,左指针从0开始,右指针从最后一个值角标开始,这样两个指针向中间靠拢,找到最大值面积。
代码:

class Solution {
    public int maxArea(int[] height) {
     int i = 0;
     int j = height.length-1;
     int area = 0;
     while(i<j){
         /*area = height[i]<height[j]?
         Math.max(area,(j-i)*height[i++])
         :Math.max(area,(j-i)*height[j--]);*/
           if(height[i]<height[j]){
               area = Math.max(area,(j-i)*height[i]);
               i++;
           }
           else{
               area = Math.max(area,(j-i)*height[j]);
               j--;
           }
     }
     return area;
    
    }
}

4.总结

在遇到这类问题时候想到的就是暴力破解,没有别的思路,还需要进行积累之前遇到过的就是设置一个boolean类型进行标记,这次是双指针。需要更多的掌握这样的技巧。
在解题的过程中,大部分都是用的while循环,语句是 左小于右 ,我当时想尝试使用for循环,遇到了以下代码:

public int maxArea(int[] a) {
		 int max = 0;
		 for(int i = 0, j = a.length - 1; i < j ; ){
			 int minHeight = a[i] < a[j] ? a[i ++] : a[j --];
			 max = Math.max(max, (j - i + 1) * minHeight);
		 }
		 return max;
	 }

我开始仿照他的思路进行写,但是其中 for语句中,我写

or(int i = 0, j = a.length - 1; i < j ;i++,j-- ){
			 int minHeight = a[i] < a[j] ? a[i ] : a[j ];
			 max = Math.max(max, (j - i + 1) * minHeight);

将i++,j-- 写到了for中 , 修改了a[i ] : a[j ],j - i + 1 或者j-i
这样反而不能得到正确答案,这点我有些不明白

	留下疑问:1.为什么for循环那个 i++ ,j-- 有问题

思路没有问题呀?


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进