力ボタンブラシ問題11.最大水容器(Java)

11.Container With Most Water最大水容器Given n non-negative integers a 1,a 2,...,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.座標の1点(i,ai)を表すn個の非負の整数a 1...anを与える.座標内にn本の垂直線を描き、垂直線iの2つの端点はそれぞれ(i,ai)と(i,0)である.x軸と共に構成された容器が最も多くの水を収容できるように、その中の2本の線を探し出す.
説明:容器を傾けることはできません.nの値は少なくとも2です.
The above vertical lines are represented by array[1,8,6,2,5,4,8,3,7].In this case,the max area of water(blue section)the container can contain is 49.図中の垂直線は入力配列を表す[1,8,6,2,5,4,8,7].この場合、容器が水を収容できる(青色部分として示す)最大値は49である.
例
入力:[1,8,6,2,5,4,8,3,7]出力:49
構想

暴力解法は1席あたりの水を盛ることができる数量を探し出して最大値(効率が人を感動させる)複雑度O(n^2)

class Solution {
 public int maxArea(int[] height) {
          int result = 0;
        int len = height.length;
        int temp = 0;
        for(int i = 0 ; i < len; i++){
            for(int j = i+1; j< len; j++){
                int min = Math.min(height[i],height[j]);
                temp = min *(j-i);
                result = (result > temp)? result : temp;
            }
        }
        return result;
    }
}

を探し出します

両指針法は針を用いて短い方を長い方向に歩かせる短い移動のみが面積を増加移動する可能性があるため長い面積を一定に縮小する

.

class Solution {
  public int maxArea(int[] height) {
           int result = 0;
           int len = height.length;
           int i = 0 , j = len-1;
           while(i < j){
               int temp = Math.min(height[i],height[j]) * (j-i);
               result = (result > temp) ? result :  temp;
               if(height[i]  height[j]){
                   j--;
               }else{
                   i++;
                   j--;
               }
           }
           return result;
       }
}