// Algorithm: two-pointer scan. Maintain leftMax and rightMax while
// 演算法：雙指針掃描。維護 leftMax 與 rightMax，
// shrinking the window from both ends. At each step, process the SHORTER side:
// 每步處理較矮的那側：該側的水量 = 該側 max - 當前高度。
// the trapped water at that cell equals sideMax - height[cell]. O(n) time, O(1) space.

int trap(int* height, int heightSize) {
    // Edge case: fewer than 3 bars cannot trap any water.
    // 邊界情況：少於 3 根柱子無法存水。
    if (heightSize < 3) return 0;

    int left = 0;                      // 左指針從最左邊開始 / left pointer starts at index 0
    int right = heightSize - 1;        // 右指針從最右邊開始 / right pointer starts at last index
    int leftMax = 0;                   // 目前左側看過的最高柱 / running max of bars seen from the left
    int rightMax = 0;                  // 目前右側看過的最高柱 / running max of bars seen from the right
    int water = 0;                     // 累積的水量 / accumulated trapped water

    // 當兩指針還沒相遇時繼續 / loop until the two pointers meet
    while (left < right) {
        // 比較兩端高度，永遠處理較矮的那邊 / always work on the shorter side
        if (height[left] < height[right]) {
            // 左邊較矮：先更新 leftMax，再用 leftMax 算這格水量
            // Left side is shorter: update leftMax first, then trap water there.
            if (height[left] >= leftMax) {
                leftMax = height[left]; // 新的左側最高 / new left-side max — this cell traps 0 water itself
            } else {
                // 左側已有更高的牆，這格能存 leftMax - height[left] 水
                // A taller wall exists on the left, so this cell traps leftMax - height[left] units.
                water += leftMax - height[left];
            }
            left++;                    // 左指針前進 / advance the left pointer
        } else {
            // 右邊較矮（或相等）：對稱地處理右側 / right side is shorter (or equal); symmetric logic
            if (height[right] >= rightMax) {
                rightMax = height[right]; // 新的右側最高 / new right-side max
            } else {
                // 右側已有更高的牆，這格能存 rightMax - height[right] 水
                // Right side already has a taller wall, so trap rightMax - height[right] units.
                water += rightMax - height[right];
            }
            right--;                   // 右指針後退 / advance the right pointer leftward
        }
    }

    return water;                      // 回傳總水量 / return the total trapped water
}