LeetCode hot100-5

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

我就是两重循环暴力解法，这样通不过，要判超时
写都写了贴一下代码

class Solution {
    public int maxArea(int[] height) {
        int maxArea = 0;
        int area = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = i + 1; j < height.length; j++) {
                area = (j - i) * Math.min(height[i], height[j]);
                if (area > maxArea) {
                    maxArea = area;
                }
            }
        }
        return maxArea;
    }
}

官方解法
双指针。l指针从前往后走，r指针从后往前走，直到相遇。什么时候l向后，什么时候r向前呢，这里需要进行一个推断。
最开始l=0，r=height.length-1. 高度分别为height[l], height[r]。 这个时候的面积是 （r-l）*min(height[l], height[r])。假设height[r] > height[l] 。 此时想要面积更大，可以如何操作呢。如果是r向前移动一格。那么乘积前面变成了（r-l-1），而乘积后面变成min(height[l], height[r-1])。height[l]是不会变的。height[r-1]>height[l]时，min(height[l], height[r-1])=height[l]；。height[r-1]<height[l]时，min(height[l], height[r-1])=height[r-1]，此时小于height[l]。也就是说乘积前面变小，乘积后面要么持平，要么继续变小。所以r向前移动是不会找到更大的面积的。而如果l向后移动的话，虽然乘积前面变小，乘积后面却有可能找到更大的数。
所以双指针就应该比较高度，然后高度小的移动，以图找到更大的面积。

public class Solution {
    public int maxArea(int[] height) {
        int l = 0, r = height.length - 1;
        int ans = 0;
        while (l < r) {
            int area = Math.min(height[l], height[r]) * (r - l);
            ans = Math.max(ans, area);
            if (height[l] <= height[r]) {
                ++l;
            }
            else {
                --r;
            }
        }
        return ans;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/container-with-most-water/solutions/207215/sheng-zui-duo-shui-de-rong-qi-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

原文地址：https://blog.csdn.net/alike_meng/article/details/136473432

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！