leetcode11.盛最多水的容器(两大详细解决方案)

2020-04-27 18:05栏目:编程
TAG: java

第一种解决方法为暴力破解:
 
 /**
     * 计算出最大值,这里就是求一个面积的最大值
     * @param height
     * @return
     */
    public static int maxArea(int[] height) {
        if (height.length < 2) {
            return 0;
        }
 
        int area = 0;
 
        // (i, height[i])
        for (int i = 0; i < height.length; i++) {
            // (j, height[j])
            for (int j = i + 1; j < height.length; j++) {
                // area = Math.min(height[i], height[j]) * (j - i);
                area = Math.max(area, Math.min(height[i], height[j]) * (j - i));
            }
        }
 
        return area;
 
    }
 
 
第二种解决方法为双指针方法,指针i最开始指向头部,指针j最开始指向尾部。因为是取矩形最大值,所以需要获取当前y轴的最小值,作为其最大值。如果height[i] < height[j], 则下次进行i++,因为进行y--只会使值越来越小,同理,大于时,则进行j--;直到 i==j之前的最后一次比较,代码如下:

 
 /**
     * 双指针方法
     * @param height
     * @return
     */
    public static int maxArea1(int[] height) {
        int length = height.length;
 
        if (length < 2) {
            return 0;
        }
 
        // 指向数组头
        int i = 0;
        // 指向数组尾
        int j = length - 1;
 
        int area = 0;
 
        // 因为最大值的宽为j - i的值,最大值的高是height[i] 和 height[j]的最小值
        // 所以对于初始时,假设固定的height[i] < height[j],对于固定至height[0],值最大就是height[0] * j
        // 所以无需比较接下来的i => j-- 的值了,所以对i进行+1与j进行比较
        while (i != j) {
            // 小端在i这边,这 j -i 最大时即为当前i的最大值
            int temp = Math.min(height[i], height[j]) * (j - i);
            if (height[i] <= height[j]) {
                i++;
            } else {
                j--;
            }
            area = Math.max(area, temp);
        }
 
        return area;
 
    }

本文来自网络,不代表山斋月平台立场,转载请注明出处: https://www.shanzhaiyue.top