// Algorithm: same two-pointer scan as the C version, written in idiomatic C++.
// 演算法：與 C 版相同的雙指針掃描，採用慣用的 C++ 寫法。
// O(n) time, O(1) extra space. We use std::vector<int> (the input type LeetCode passes in)
// and the standard std::max from <algorithm>.

#include <vector>      // std::vector 動態陣列 / dynamic array container
#include <algorithm>   // std::max 取最大值的工具函式 / utility function for max

class Solution {
public:
    // 函式簽名：接收一個整數向量的 const 參考（避免複製），回傳 int
    // Signature: take a const reference to a vector<int> (no copy), return int.
    int trap(const std::vector<int>& height) {
        const int n = static_cast<int>(height.size()); // 取得長度，轉成 int 方便比較 / size as int
        if (n < 3) return 0;                            // 少於 3 根柱子無法存水 / not enough bars to trap water

        int left = 0;                  // 左指針 / left pointer
        int right = n - 1;             // 右指針 / right pointer
        int leftMax = 0;               // 左側最高柱 / running max from the left
        int rightMax = 0;              // 右側最高柱 / running max from the right
        int water = 0;                 // 答案累加器 / accumulator for trapped water

        // 雙指針向中間靠攏 / pointers move toward each other until they meet
        while (left < right) {
            if (height[left] < height[right]) {
                // 左側較矮 → 處理左格 / left side is shorter, process the left cell
                // std::max(a, b) 回傳 a 與 b 中較大者 / returns the larger of a and b
                leftMax = std::max(leftMax, height[left]);
                water += leftMax - height[left]; // 若 height[left]==leftMax 則加 0 / adds 0 when this cell IS the wall
                ++left;                          // 前綴遞增運算子，比 left++ 略快一些 / pre-increment, idiomatic in C++
            } else {
                // 右側較矮或相等 → 處理右格 / right side is shorter or equal, process the right cell
                rightMax = std::max(rightMax, height[right]);
                water += rightMax - height[right]; // 對稱地累加水量 / symmetric accumulation
                --right;                            // 右指針往左移 / move right pointer leftward
            }
        }

        return water; // 回傳結果 / return the total trapped water
    }
};