[数据结构与算法]2021-08-11今日题解

盛最多水的容器

最近做的题里处理的大量数据的题还是蛮多的，今天就挑一个稍微简单点的说一下。这个题看上去还是挺简单的，因为题目表达得很清楚跟着题目模拟就可以，但是很容易就写出n平方的时间复杂度，而这个题的数据量还是蛮大的所以这样处理肯定不行。

public int maxArea(int[] height) {
        int max=Integer.MIN_VALUE;
        for (int i = 0; i < height.length; i++) {
            for (int j = i+1; j < height.length; j++) {
                max=Integer.max(max,(j-i)*Integer.min(height[j],height[i]));
            }
        }
        return max;
    }

这是我一开始写的代码，不出意外的它超时了，于是我就开始想应该怎么改进，按道理来说应该是挺好改进的，然后我就开始想着应该怎么修改这个循环才能减少循环次数，想要找到线性时间复杂度得到算法，于是我就在想（想偏了 ）只移动一边通过预先判断移动后与移动前的大小来确定最大值，很明显这是错的，但是在改的时候我想到了移动两个指针可不可以，通过预先判断移动最优的一边，这样的话就避免了无谓的组合，而且也会遍历所有可能的组合，然后这个题就出来了。

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