[Leetcode]Container With Most Water随记

这道题目在坐标轴中给出了若干平行于y轴的竖线，每两个搭配加上x轴组成一个盛水的容器，找出容量最大的容器。

最暴力的方法还是两重循环算，这不在我们讨论范围内。

这里采用贪心算法实现，在该题中有一个规律，如果说最终的结果是ij两个竖线组成的容器最大（假设i<j），那么在i的左边肯定没有比i更高的线，j的右边肯定没有比j更高的线（因为一旦存在，那肯定更高的线组成的容器容量大，它不光墙壁高，x轴占得宽度也大）。那么我们只需要从两头开始遍历，设左右下标为i和j，如果i比j高，那么j--，否则i++。（可以这样设想，由于我们是贪心算法，如果遇到i比j低的情况，j的来源也是由于它比某个i左边的低才会移动到j现在的位置，那么既然i的左边存在比i高的，肯定是那条线和j组成的容器更大，所以i直接被忽略即可）。

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

[Leetcode]Container With Most Water随记

推荐阅读