每日一题-盛最多水的容器-0716

题目

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。

思路

• 一个下标从左开始走，另一个下标从右开始走。对比两边柱子的高度，因为装水，所以较矮的一边是容器的高度。
• 当前能装的最大体积，就是min(height[left], height[right])*(right-left)，用过的一边就需要向前进，再找当前的最大体积。
• 同时需要一个变量，不断的去更新这个容器能装水的最大值。res = Math.max(res, min(height[left], height[right])*(right-left))

代码

public int maxArea(int[] height) {
    
        if(height == null || height.length == 0)
            return 0;
        int res = 0;
        int left = 0, right = height.length - 1;
        // 不断的迭代容器可以盛水的最大值
        while(left < right){
    
            res = height[left] > height[right] ? Math.max(res, (right - left) * height[right --]) :
                    Math.max(res, (right - left) * height[left ++]);
        }
        return res;
    }