題目連結

題型解說

這是一題難度為中等的題目

需要設計一個方法，此方法會傳入一個數字陣列 height

陣列中的元素代表每一個柱子的高度

現在需要計算出，該陣列中以某兩隻柱子為邊界，最多可以裝多少水

以範例來說 height = [1,8,6,2,5,4,8,3,7]

最多可以裝 7 * 7 = 49 單位的水

解題思路

計算面積就是底乘上高

底的計算方式為 「右邊柱子的 index」 減去 「左邊柱子的 index」

高就取最短的那一根柱子高度

拿題目給的例子來當範例

建立三個變數 result、left、right

left、right 代表左右兩邊的 index

result 代表目前最大容量，初始值 0

第一步，找出最短的柱子高度，計算出面積

底(8-0) * 高(1) = 面積(8)

和 result 比較，取最大值存入 result

將上一步的最短柱子的 index 往後(前)，再計算面積

底(8-1) * 高(7) = 面積(49)

和 result 比較，取最大值存入 result

將上一步的最短柱子的 index 往後(前)，再計算面積

底(7-1) * 高(3) = 面積(18)

和 result 比較，取最大值存入 result

將上一步的最短柱子的 index 往後(前)，再計算面積

底(6-1) * 高(8) = 面積(40)

和 result 比較，取最大值存入 result

將上一步的最短柱子的 index 往後(前)，再計算面積

底(6-2) * 高(6) = 面積(24)

和 result 比較，取最大值存入 result

將上一步的最短柱子的 index 往後(前)，再計算面積

底(6-3) * 高(2) = 面積(6)

和 result 比較，取最大值存入 result

將上一步的最短柱子的 index 往後(前)，再計算面積

底(6-4) * 高(5) = 面積(10)

和 result 比較，取最大值存入 result

將上一步的最短柱子的 index 往後(前)，再計算面積

底(6-5) * 高(4) = 面積(4)

和 result 比較，取最大值存入 result

直到 left、right 重疊後就結束計算，回傳 result

程式碼

Java

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

        while (left < right) {
            int _left = height[left];
            int _right = height[right];

            if (_left < _right) {
                result = Math.max(result, _left * (right - left));
                left++;
            } else {
                result = Math.max(result, _right * (right - left));
                right--;
            }
        }

        return result;
    }
}