//package com.stack;
//
//import jdk.nashorn.internal.ir.IdentNode;
//
//import java.util.*;
//
//public class MaxWaterCapacity {
//
// // 使用单调栈求解
// public static int trap1(int[] height) {
// if (height == null || height.length == 0){
// return 0;
// }
//// Stack<Integer> stack = new Stack<>();
// Deque<Integer> stack = new LinkedList<>();
// int ans = 0;
// for (int i = 0;i < height.length;i++){
// // 注意这里的判断条件是height[i] > height[stack.peek()],
// // 即当height[i] < height[stack.peek()]时,不进行面积求解
// while (!stack.isEmpty() && height[i] > height[stack.peek()]){
// int top = stack.pop();
// if (stack.isEmpty()){
// break;
// }
// int left = stack.peek();
// int curWidth = i - left - 1;
// int curheight = Math.min(height[i],height[left]) - height[top];
// ans += curWidth * curheight;
// }
// stack.push(i);
// }
// return ans;
// }
//
// // 双向指针
// public static int trap2(int[] height) {
// if (height == null || height.length == 0){
// return 0;
// }
// int left = 0;
// int right = height.length -1;
// int leftMax = 0;
// int rightMax = 0;
// int res = 0;
// while (left < right){
// leftMax = Math.max(leftMax,height[left]);
// rightMax = Math.max(right,height[right]);
// if (height[left] < height[right]){
// res += leftMax - height[left];
// ++left;
// }else {
// res += rightMax - height[right];
// --right;
// }
// }
// return res;
// }
//
// // 动态规划
// public static int trap3(int[] height) {
// if (height == null || height.length == 0){
// return 0;
// }
// int N = height.length;
// int[] leftArr = new int[N];
// int[] rightArr = new int[N];
// int res = 0;
//
// leftArr[0] = height[0];
// for (int i = 1;i < N;i++){
// leftArr[i] = Math.max(leftArr[i-1],height[i]);
// }
//
// rightArr[N-1] = height[N -1];
// for (int i = N-2; i >= 0; i--) {
// rightArr[i] = Math.max(rightArr[i+1],height[i]);
// }
//
// for (int i = 1;i < N;i++){
// res += Math.min(leftArr[i],rightArr[i]) - height[i];
// }
// return res;
// }
//
//
//
//
//
//
// public static void main(String[] args) {
//
// }
//}