</> ᴍᴜᴋᴇsʜ </>
TrapRainWater Code time complexibilty O(n)
public class traprainwat {
public static int trapwater(int height[]) {
// left max
int n = height.length;
int leftMax[] = new int[n];
leftMax[0] = height[0];
for (int i = 1; i < n; i++) {
leftMax[i] = Math.max(height[i], leftMax[i - 1]);
}
// for (int i = 0; i < n; i++) {
// System.out.print(leftMax[i]);
// }
// right max
int rightMax[] = new int[n];
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i--) {
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}
// for (int i = 0; i < rightMax.length; i++) {
// System.out.print(rightMax[i]);
// }
// loop
int traprainw = 0;
for (int i = 0; i < n; i++) {
// waterlevel=min(leftmax,rightmax)
int waterlevel = Math.min(leftMax[i], rightMax[i]);
// traprainwater=waterlevel-height[i]
traprainw += waterlevel - height[i];
}
return traprainw;
}
public static void main(String[] args) {
int height[] = { 4, 2, 0, 6, 3, 2, 5 };
System.out.println(trapwater(height));
}
}
Output:
11
5 · 2.7K ·