Решить задачу Trapping Rain Water (LeetCode 42)?

LeetCode 42. Сколько воды удержится между столбцами. Water at i = max(0, min(max_left, max_right) - height[i]). Two pointers — O(n) время, O(1) память.

def trap(height):
    if not height:
        return 0
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0
    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1
    return water

Альтернатива — DP с prefix/suffix max: для каждого i предпосчитать max_left[i] и max_right[i], O(n) время и O(n) память. Идея two pointers: двигая меньший указатель, гарантируем, что left_max/right_max — реальная граница. Третий подход — monotonic stack.