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.

難易度:　medium
入力:　int型Array
目的: 入力されたi番目の整数をaiとし、x軸とai, ajで樽を作り一番多く水を汲める体積を求めよ
出力:　int

難易度medium
問題自体は簡単ですが英語に苦戦する人も多いと思います。
入力はアレイで例えば[1,4,5,2,9]が入力されるとします。
それぞれの入力数字が一つの座標を示します。
[1,4,5,2,9]の場合、(1,1), (2,4), (3,5), (4,2), (5,9)と、i番目の数字が(i,height[i])を表します。
その点とx軸の間を垂直線で結び、樽を組みます。
樽で水を汲むとして、最大でどれくらいの水を汲めるかと言う問題です。
画像で表しますと：

的な感じです。
青色の棒が入力数値とx軸との垂直線で、
赤い棒が今樽に組まれている棒です。
水色で囲まれている部分が今使っている棒で汲める水の面積になります。

注意すべき事:　

• 水の高さは短い方の棒の長さで決まります。

以下回答です。

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

比較的簡単な問題です。
一番端っこから樽を作っていき、短い方の棒を破棄して内側に進むと言う考えです。
Time complexity はO(n), SpaceはO(1)です。
もう一つの方法として、
すべての組み合わせを試し最大値を求める方法がありますが、
時間がO(n^2)になってしまうのでパス出来ないでしょう。

では！