双指针思想

/* gcc main.c -o main.exe */

# include <stdio.h>

# define max(a, b) (a > b ? a : b)

int Trap(int* height, int heightSize) {
    int ans = 0;
    int* left = &height[0];
    int* right = &height[heightSize-1];
    int leftMaxHeight = 0, rightMaxHeight = 0;
    while (left < right) {
        leftMaxHeight = max(*left, leftMaxHeight);
        rightMaxHeight = max(*right, rightMaxHeight);
        if (*left < *right) {
            ans = ans + (leftMaxHeight - *left);
            ++left;
        } else {
            ans = ans + (rightMaxHeight - *right);
            --right;
        }
    }
    return ans;
}

int main() {
    printf("\033[H\033[J");
    int height[] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    int heightSize = sizeof(height) / sizeof(height[0]);
    int ans = Trap(height, heightSize);
    printf("%d", ans);
    return 0;
}

# Python 3.10.0 +

def Trap(height: list[int]) -> int:
    ans = 0
    left = 0
    right = ~-len(height)
    leftMax = rightMax = 0
    # 当左指针索引小于右指针索引.
    while left < right:
        # 从 leftMax 和左指针元素中取一个最大值, 即左边目前为止最高值.
        leftMax = max(leftMax, height[left])
        # 从 rightMax 和右指针元素中取一个最大值, 即右边目前为止最高值.
        rightMax = max(rightMax, height[right])
        # 取决于短板, 谁低谁在的那边加水.
        if height[left] < height[right]:
            ans = ans + (leftMax - height[left])
            left = -~left
        else:
            ans = ans + (rightMax - height[right])
            right = ~-right
    return ans

print(Trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))