【LeetCode】11. Container With Most Water

题目：

　　Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

　　Note: You may not slant the container.

翻译：

　　给定n个非负整数a1,a2,...,an，其中每个代表一个点坐标（i,ai）。 n个垂直线段例如线段的两个端点在（i,ai）和（i,0）。找到两个线段，与x轴形成一个容器，使其包含最多的水。

　　备注：不考虑倾斜容器。

思路：容积其实就是面积，我们都知道长方形的面积=长*宽，不妨我们就从长最长的长方形找起，即令left = 0， right = height.size() - 1，但是在找下一个长方形时，长肯定会变短，要弥补这一段损失就必须加宽宽度，所以一下个就换掉两条宽中较小的那一个。

public class Solution {

    public int maxArea(int[] height) {

        int left=0;

        int right=height.length-1;

        int maxArea=0;

        while(left<right){

            maxArea=Math.max(maxArea,Math.min(height[left],height[right])*(right-left));

            if(height[left]>height[right]){

                right--;

            }else{

                left++;

            }

        }

        return maxArea;

    }

}

巴特西

【LeetCode】11. Container With Most Water

最新文章

热门文章