package question;

import java.util.Deque;
import java.util.LinkedList;
import java.util.concurrent.ArrayBlockingQueue;

/**
 * @author Roderland
 * @since 1.0
 */
public class Question42 {
 public static void main(String[] args) {
 System.out.println(new Question42().trap4(new int[]{
 4, 2, 3
 }));
 }


 public int trap4(int[] height) {
 int res = 0;
 int[] maxR = new int[height.length];
 for (int i = height.length - 2; i >= 0; i--) {
 maxR[i] = Math.max(maxR[i + 1], height[i + 1]);
 }
 int maxL = 0;
 for (int i = 1; i < height.length - 1; i++) {
 maxL = Math.max(maxL, height[i - 1]);
 int h = Math.min(maxL, maxR[i]);
 res += h > height[i] ? h - height[i] : 0;
 }
 return res;
 }

 public int trap3(int[] height) {
 int res = 0;
 int[] maxL = new int[height.length];
 int[] maxR = new int[height.length];
 for (int i = height.length - 2; i >= 0; i--) {
 maxR[i] = Math.max(maxR[i + 1], height[i + 1]);
 }
 for (int i = 1; i < height.length; i++) {
 maxL[i] = Math.max(maxL[i - 1], height[i - 1]);
 }
 for (int i = 1; i < height.length - 1; i++) {
 int h = Math.min(maxL[i], maxR[i]);
 res += h > height[i] ? h - height[i] : 0;
 }
 return res;
 }

 public int trap2(int[] height) {
 int res = 0;
 for (int i = 1; i < height.length - 1; i++) {
 int left = 0;
 for (int j = i - 1; j >= 0; j--) {
 left = Math.max(left, height[j]);
 }
 int right = 0;
 for (int j = i + 1; j < height.length; j++) {
 right = Math.max(right, height[j]);
 }
 int h = Math.min(left, right);
 res += h > height[i] ? h - height[i] : 0;
 }
 return res;
 }

 public int trap1(int[] height) {
 int res = 0;
 while (true) {
 int left = -1;
 int right = -1;
 for (int i = 0; i < height.length; i++) {
 if (height[i] > 0) {
 left = i;
 break;
 }
 }
 for (int i = height.length - 1; i >= 0; i--) {
 if (height[i] > 0) {
 right = i;
 break;
 }
 }
 if (left == -1 || right == -1 || left == right) break;
 for (int i = 0; i < height.length; i++) {
 if (height[i] == 0 && i > left && i < right) res++;
 else height[i]--;
 }
 }
 return res;
 }
}