Brute Force
class Solution {
public int trap(int[] height) {
int res = 0;
int n = height.length;
for (int i = 1; i < n - 1; i++) {
int leftMax = 0, rightMax = 0;
for (int j = i; j < n; j++) {
rightMax = Math.max(rightMax, height[j]);
}
for (int j = i; j >= 0; j--) {
leftMax = Math.max(leftMax, height[j]);
}
res += Math.min(leftMax, rightMax) - height[i];
}
return res;
}
}
Dynamic Programming (Memorization)
class Solution {
public int trap(int[] height) {
int n = height.length;
if (n == 0) {
return 0;
}
int[] leftMax = new int[n];
int[] rightMax = new int[n];
// init
leftMax[0] = height[0];
rightMax[n - 1] = height[n - 1];
// calculate leftMax from left to right
for (int i = 1; i < n; i++) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
// calculate rightMax from right to left
for (int i = n - 2; i >= 0; i--) {
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}
int res = 0;
for (int i = 1; i < n - 1; i++) {
res += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return res;
}
}
Dynamic Programming (Two Pointers and State Space Reduction)
class Solution {
public int trap(int[] height) {
int n = height.length;
if (n == 0) {
return 0;
}
int leftMax = height[0];
int rightMax = height[n - 1];
int left = 0, right = n - 1;
int res = 0;
while (left <= right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if (leftMax < rightMax) {
res += leftMax - height[left];
left++;
} else {
res += rightMax - height[right];
right--;
}
}
return res;
}
}