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 and n is at least 2.
翻訳
n個の非負の整数a 1,a 2...,anは、各座標点(i,ai)を表す.i行の2つの端点が(i,ai)と(i,0)になるようにn個の垂直線を描く.2本の線を見つけて、x軸とともに容器を形成し、容器に最も多くの水を収容させる.注意:容器を傾けてはいけません.nは少なくとも2です.
例:
入力:(1,2),(2,3),(3,1),(4,5),(5,4)出力:8
分析:
暴力的な方法は容易に考えられる:各縦線と他の各縦線からなるバケツの面積を求め、それから最大の面積を求めればよく、明らかに時間複雑度はO(n 2)である.この問題にはもう一つの解法がある.iとjがそれぞれ与えられたx座標軸の下付き記号である場合、iheight[i]、f(i+1,j)=height[i]*(j-i-1)であるため、f(i+1,j)height[j]は、f(i,j−1)=height[i]*(j−i−1)であるため、f(i,j−1)=height[j]についてはf(i+1,j)とf(i,j)の大きさを判断するだけでよいと分析できる.
コード:

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