LeetCode Note Java 00011：Container With Most Water

發表於 更新於 分類於 ， ， ， 閱讀次數： Disqus： 0 Comments 文章字數： 277 所需閱讀時間 ≈ 1 分鐘

情境題：給定一系列長短不一的高，每個高坐落於間格為 1 的 x 軸上，求任意兩個高夾出的最大裝水容積。

題目

Container With Most Water Medium

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

我的解法

暴力解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        for (int i = 0; i < height.length - 1; i++) { // i means left border
          for (int j = i + 1; j < height.length; j++) { // j means right border
            int y = height[i] <= height[j] ? height[i] : height[j];
            int x = j - i;
            int volume = x * y;
            max = volume > max ? volume : max;
          }
        }
        return max;
    }
}

會超時。

Two Pointer：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxArea(int[] height) {
        int l = 0, r = height.length - 1;
        int result = 0;
        while (l < r) {
          int x = r - l;
          int y = Math.min(height[l], height[r]);
          int area = x * y;
          result = Math.max(area, result);
          if (height[l] < height[r]) { // 這邊比較難說服自己腦袋，但主要概念還是留住最大的值
            l++;
          } else {
            r--;
          }
        }
        return result;
    }
}

參考資料

leetcode/java/0011-container-with-most-water.java