今天來講解第11題

題目

題目翻譯

請寫一個方法，輸入一個int陣列，陣列內的數字代表牆的高度，請輸出兩道牆之間最多可以存的水量

解題思路

1. 初始化雙指針：

   • 設置兩個指針：left 指向容器左側（索引 0），right 指向容器右側（索引 height.size() - 1）。
   • 初始化變數 ans，用來儲存最大水量。

2. 計算當前水量：

   • 使用公式 min(height[left], height[right]) * (right - left) 計算兩個指針之間能容納的水量：
     • 取 height[left] 和 height[right] 中較小的高度作為有效高度，乘以兩者之間的距離 right - left。

3. 更新最大水量：

   • 將當前計算出的水量與目前存儲的最大水量 ans 比較，若當前水量較大，則更新 ans。

4. 移動指針：

   • 比較 height[left] 和 height[right]：
     • 如果 height[left] 較低，則向右移動 left 指針（left++），希望找到更高的柱子來增加水量。
     • 如果 height[right] 較低，則向左移動 right 指針（right--），同樣期望增加水量。

5. 停止條件：

   • 當 left 和 right 指針相遇時，迴圈結束，因為此時所有可能的區間都已經計算過。

6. 返回結果：

   • 返回 ans，即過程中計算出的最大水量。

code

class Solution {
public:
    int maxArea(vector<int>& height) {
        int ans = 0; // 儲存最大水量
        int left = 0, right = height.size() - 1; // 左右指針

        while (left < right) {
            // 計算當前區間容納的水量
            int temp = min(height[left], height[right]) * (right - left);
            ans = max(ans, temp); // 更新最大值

            // 移動指針：總是移動較矮的那一邊，期望獲得更大的容積
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return ans; // 返回最大水量
    }
};