LeetCode. 11. 盛れる水の最大量

問題: Container With Most Water

2ポインター

l < rとなる2つの添字を選ぶと、容器に入る水の高さは2本の線のうち低い方で決まります。幅はr - l、高さはmin(height[l], height[r])なので、面積は次の式です。

配列の両端から始めます。この2本は取り得る最大幅の容器を作ります。面積を記録したら、低い方の線を指すポインターを内側へ動かします。高さが等しい場合はどちらを動かしてもよく、以下の実装では右ポインターを動かします。

低い方を捨てても最適解を逃さない理由

height[l] <= height[r]とします。現在の容器の高さはheight[l]以下です。lを固定して右端をr' < rにすると、幅はr-lより小さくなります。また、左側の壁は変わらずheight[l]なので、高さがheight[l]を超えることもありません。したがって、その面積は現在の面積を超えません。lを使いながらrより内側に端点を置いても、よりよい答えにはなりません。そのためlを捨てて右へ進めます。右側の方が低い場合も対称的に同じ議論が成り立ちます。これを繰り返せば、よりよい可能性のある組み合わせを見落としません。

Java実装

制約は2 <= height.length <= 10^5、0 <= height[i] <= 10^4です。よって最大面積は(10^5 - 1) * 10^4 = 999,990,000以下で、符号付き32ビットのintに収まります。乗算と結果の両方をintで扱っても安全です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int best = 0;

        while (left < right) {
            int area = (right - left) * Math.min(height[left], height[right]);
            best = Math.max(best, area);

            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return best;
    }
}

各ポインターは最大N回だけ内側へ移動するため、時間計算量はO(N)、追加領域はO(1)です。