leetcode练习题11-盛水最多的容器
2020-12-12 / highPhone啊

这是leetcode题库的第11题 - 盛水最多的容器

解题思路

盛水面积 = 长(两条边的数组下标之差的绝对值) x 宽(两条变的高度中较小的一条边)

  1. 以官方第一个示例作为分析，我们可以用两个指针分别指向数组的第一个元素和最后一个元素，即left为0，right为height.length -1,初始容积是 (height.length -1 -0) * min(height[0], height[height.length-1]),上图中即是(8-0) x 1 = 8;
  2. 然后用双指针i, j遍历height数组。对于height[i]和height[j]两条边，我们总是期望能保留比较高的一条边，然后放弃比较低的一条边，另寻一条相对比较高的边来使容积增大。
  3. 因此，我们在获取初始面积后，如果height[i] < height[j],那我们尝试i + 1，去找一条更高的变，i+1 后，再按照步骤1的计算方法计算新的容器的容积，如果计算结果比现有的大，那就把i赋值给left。同理如果height[i] > height[j],那我们尝试j - 1，去找一条更高的变，j-1 后，再按照步骤1的计算方法计算新的容器的容积，如果计算结果比现有的大，那就把j赋值给right。
  4. 当遍历完height数组(i >= j)，left和right指针就分别指向了容积最大两条边，即可按照步骤1的计算方法算出最大容积area返回。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int maxArea(int[] height) {
    int area = 0;
    if(height != null && height.length > 1)//注意处理边界条件
    {
        int left = 0;//最大容积的左边指针
        int right = height.length -1;//最大容积的右边指针
        for (int i = 0, j = height.length -1; i < j;) {
            if(((j-i) * Math.min(height[i], height[j])) > ((right - left) * Math.min(height[right], height[left])))
            {
                //如果此次计算的容积比现有的大，即把i赋值给left，j赋值给right，更新现有的最大容积指针
                left = i;
                right = j;
            }
            //如果此次计算容积比现有小，把数值小的一边舍弃，寻找数值更大的边。
            if(height[i] > height[j])
            {
                j--;
            }
            else{
                i++;
            }
        }
        area = (right -left) * (Math.min(height[left], height[right]));//计算最终最大容积
    }
    return area;
}
本文链接：https://highphone.xyz/a25ed364.html