盛最多水的容器

盛最多水的容器

题目分析

给定一个数组，数组中的值代表桶高，找到数组中的两个值，使其和x轴围起来的部分可以盛最多的水；

分析题目中，题目没有明确告知数组中数组的大小顺序，这是其一，其二，数组中的值代表桶高，根据短木桶原则，因此桶高只能取小者；

使用双指针法

1647671366325

目标是求区间面积的最大值，所以，需要在两端分别设计一个指针向中间移动，移动一次求出一个面积。

• 每次遍历，都判断面积是否是最大的，取最大即可。
• 但是在双指针向中间移动过程中，需要判断一下，哪一个指针元素对应的元素值小，先移动哪一个指针，因为我们要求所有可求的区间面积的最大值。

go实现

func maxArea_A(height []int) int {

	left := 0
	right := len(height) - 1
	var res int
	for left < right {
		i := height[left]
		j := height[right]
		maxArea := (right - left) * min(i, j)
		res = max(res, maxArea)
		if i < j {
			left++
		} else {
			right--
		}

	}
	return res
}

/*返回最大值和最小值函数*/
func min(a int, b int) int {
	if a > b {
		return b
	}
	return a
}
func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

java实现

class Solution {
    public int maxArea(int[] height) {

        return maxArea_A(height);
    }

//使用双指针
    public int maxArea_A(int []height){

        int sz = height.length;
        if(sz ==0){
            return 0;
        }
        int left = 0;
        int right = sz-1;
        int maxArea = 0;
        while(left < right){
            int area = (right-left)*Math.min(height[left],height[right]);           
            maxArea = Math.max(maxArea,area);
            // 下面类似于二分查找
            if(height[left] < height[right]){
                left++;
            }else{
                right--;
            }
            
        }

        return maxArea;
    }
}

时间复杂度：o(n)