Trapping the Rainwater is a classical algorithmic
problem. It finds the trapping water on the elevation map. Here, the elevation
map is implemented by an array as stack.
Let us implement this algorithm in Java.
- First,
create an integer array for storing the stack. Each element represents a
bar in the elevation map. The bar represents the count of trapping water
after the rain.
- Initialize
the two pointers. One points to the left side, and another points to the
right side of the array.
- Find
the maximum height of the right and left side of the array and store it in
two variables.
- Finally,
calculate the trapped water value by moving the pointers towards the
center. It’s time to find the maximum and minimum values from the left and
right.
Java Implementation
public class TrapitRainWater {
public static int
trapit(int[] h) {
if (h == null
|| h.length == 0) {
return 0;
}
int Tleft = 0,
Tright = h.length - 1;
int TleftMax =
0, TrightMax = 0;
int trappedvalue
= 0;
while (Tleft
< Tright) {
if
(h[Tleft] < h[Tright]) {
if
(h[Tleft] >= TleftMax) {
TleftMax = h[Tleft];
} else
{
trappedvalue += TleftMax - h[Tleft];
}
Tleft++;
} else {
if
(h[Tright] >= TrightMax) {
TrightMax = h[Tright];
} else
{
trappedvalue += TrightMax - h[Tright];
}
Tright--;
}
}
return
trappedvalue;
}
public static void
main(String[] args) {
int[] h = {1,
0, 2, 3, 4, 1, 0, 3, 1, 0, 3, 2};
int finalvalue
= trapit(h);
System.out.println("The count of the trapped water is: " +
finalvalue);
}
}
Output:
C:\raji\blog>javac TrapitRainWater.java
C:\raji\blog>java TrapitRainWater
The count of the trapped water is: 11
This is the way of implementing trapping the rain water
using stack in Java. Keep coding!!!
If you need any more help with this algorithm or others, feel free to ask!
No comments:
Post a Comment