11.最も水を盛る容器Leetcode Java実現

タイトル:
n個の非負の整数a 1,a 2,...,anは、各数が座標の1つの点(i,ai)を表す.座標内にn本の垂直線を描き、垂直線iの2つの端点はそれぞれ(i,ai)と(i,0)である.x軸と共に構成された容器が最も多くの水を収容できるように、その中の2本の線を探し出す.
説明:容器を傾けることはできません.nの値は少なくとも2です.
2つの方法があります.
方法1:暴力法
すべての状況を全部歩いて、最大面積を見つけます.

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

時間複雑度:O(n^2).

空間複雑度:O(1)で、一定の空間を使用します.

方法2:
両指針法を用い,バケツ効果(短板理論とも呼ばれる)によりバケツの容量が最短板に決定されるため,両端にl,rの2つのポインタを設け,(r−l)を底とし,両端の高さが短い方を高さとし,誰が短いかを中間に移動させて最大容量を算出する.

class Solution {
    public int maxArea(int[] height) {
        int maxArea=0,l=0,r=height.length-1;
        while(l

時間複雑度:O(n),一次走査.

空間複雑度:O(1)で、一定の空間を使用します.