Java 求解盛最多水的容器

文章目录

一、题解

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

---

设置双指针 left,right 分别位于容器壁两端，根据规则移动，更新面积max,直到 left==right，返回 max。

移动规则：每次选定围成水槽两班高度h[left]，h[right]中的短板，向中间收窄一格。

• 由于水槽的实际高度由两板中的短板决定：S(left,right)=min(h[left],h[right])*(right-left)
• 每一个状态，无论长板还是短板收窄一格，都会导致水槽底边宽度-1：
  • 若向内移动短板，水槽的短板 min(h[left],h[right])可能变大，因此水槽面积S可能变大
  • 若向内移动长板，水槽短板不变或者变小，下个水槽的面积一定小于当前水槽的面积。

因此向内收窄短板可以获取面积最大值

二、代码

public class Test {
    public static void main(String[] args) {
        int[] height = {1, 2, 1};
        int result = maxArea(height);
        System.out.println(result);
    }

    private static int maxArea(int[] height) {
        //设置左右指针
        int left = 0, right = height.length - 1;
        int max = 0;
        //左右指针中的短板移动
        while (left < right) {
            max = height[left] < height[right] ?
                    Math.max(max, (right - left) * height[left++]) :
                    Math.max(max, (right - left) * height[right--]);
        }
        return max;
    }
}

三、总结

注意三目运算的使用

除了双指针法，还可以使用暴力解决法。

class Solution {
    public int maxArea(int[] height) {
        if(height==null || height.length==0 || height.length==1){
            return 0;
        }
        int max = 0;
        for(int i=1;i<height.length;i++){
            for(int j=0;j<i;j++){
                int temp = area(height,j,i);
                if(temp > max){
                    max = temp;
                }
            }
        }
        return max;
    }
    public int area(int[] height,int j,int i){
        return height[j]>height[i]?height[i]*(i-j):height[j]*(i-j);
    }
}

本文地址：https://blog.csdn.net/nanhuaibeian/article/details/110109951