• Time:O(n)
• Space:O(n)

## C++

``````class Solution {
public:
int trap(vector<int>& height) {
const int n = height.size();
int ans = 0;
vector<int> l(n);  // l[i] := max(height[0..i])
vector<int> r(n);  // r[i] := max(height[i..n))

for (int i = 0; i < n; ++i)
l[i] = i == 0 ? height[i] : max(height[i], l[i - 1]);

for (int i = n - 1; i >= 0; --i)
r[i] = i == n - 1 ? height[i] : max(height[i], r[i + 1]);

for (int i = 0; i < n; ++i)
ans += min(l[i], r[i]) - height[i];

return ans;
}
};
``````

## JAVA

``````class Solution {
public int trap(int[] height) {
final int n = height.length;
int ans = 0;
int[] l = new int[n]; // l[i] := max(height[0..i])
int[] r = new int[n]; // r[i] := max(height[i..n))

for (int i = 0; i < n; ++i)
l[i] = i == 0 ? height[i] : Math.max(height[i], l[i - 1]);

for (int i = n - 1; i >= 0; --i)
r[i] = i == n - 1 ? height[i] : Math.max(height[i], r[i + 1]);

for (int i = 0; i < n; ++i)
ans += Math.min(l[i], r[i]) - height[i];

return ans;
}
}
``````

## Python

``````class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
l = [0] * n  # l[i] := max(height[0..i])
r = [0] * n  # r[i] := max(height[i..n))

for i, h in enumerate(height):
l[i] = h if i == 0 else max(h, l[i - 1])

for i, h in reversed(list(enumerate(height))):
r[i] = h if i == n - 1 else max(h, r[i + 1])

return sum(min(l[i], r[i]) - h
for i, h in enumerate(height))
``````

• Time:O(n)
• Space:O(1)

## C++

``````class Solution {
public:
int trap(vector<int>& height) {
if (height.empty())
return 0;

int ans = 0;
int l = 0;
int r = height.size() - 1;
int maxL = height[l];
int maxR = height[r];

while (l < r)
if (maxL < maxR) {
ans += maxL - height[l];
maxL = max(maxL, height[++l]);
} else {
ans += maxR - height[r];
maxR = max(maxR, height[--r]);
}

return ans;
}
};
``````

## JAVA

``````class Solution {
public int trap(int[] height) {
if (height.length == 0)
return 0;

int ans = 0;
int l = 0;
int r = height.length - 1;
int maxL = height[l];
int maxR = height[r];

while (l < r)
if (maxL < maxR) {
ans += maxL - height[l];
maxL = Math.max(maxL, height[++l]);
} else {
ans += maxR - height[r];
maxR = Math.max(maxR, height[--r]);
}

return ans;
}
}
``````

## Python

``````class Solution:
def trap(self, height: List[int]) -> int:
if not height:
return 0

ans = 0
l = 0
r = len(height) - 1
maxL = height[l]
maxR = height[r]

while l < r:
if maxL < maxR:
ans += maxL - height[l]
l += 1
maxL = max(maxL, height[l])
else:
ans += maxR - height[r]
r -= 1
maxR = max(maxR, height[r])

return ans
``````