Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- <?php
- function trappingRainWater($arr) {
- $n = count($arr);
- $water = 0;
- // $left[i] menyimpan nilai maksimum
- // dari array
- $left = [0];
- // proses array dari kiri ke kanan
- // dari current bar
- for ($i = 1; $i < $n - 1; $i++) {
- $left[$i] = max($left[$i - 1], $arr[$i - 1]);
- }
- // $right menyimpan tinggi max ke kanan
- // dari current bar
- $right = 0;
- // process perhitungan dari kanan ke kiri
- for ($i = $n - 2; $i >= 1; $i--) {
- $right = max($right, $arr[$i + 1]);
- // cek kemungkinan untuk menampung air pada current bar
- if (min($left[$i], $right) > $arr[$i]) {
- $water += min($left[$i], $right) - $arr[$i];
- }
- }
- return $water;
- }
- // Main
- $arr = [];
- echo implode(',', $arr) . ' = ' . trappingRainWater($arr);
- echo "\n";
- $arr = [0,1,0];
- echo implode(',', $arr) . ' = ' . trappingRainWater($arr);
- echo "\n";
- $arr = [2,1,3];
- echo implode(',', $arr) . ' = ' . trappingRainWater($arr);
- echo "\n";
- $arr = [0,1,0,2,1,0,1,3,2,1,2,1];
- echo implode(',', $arr) . ' = ' . trappingRainWater($arr);
- echo "\n";
- $arr = [2,1,0,2,1,0,1,3,5,1,3,10];
- echo implode(',', $arr) . ' = ' . trappingRainWater($arr);
- echo "\n";
- $arr = [12,1,0,2,1,0,1,3,5,1,3,10];
- echo implode(',', $arr) . ' = ' . trappingRainWater($arr);
- echo "\n";
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement