package com.q0042;

import java.util.ArrayDeque;

import java.util.Arrays;

import java.util.Deque;

/**

* @author xjn

* @since 2020-05-28

* https://leetcode-cn.com/problems/trapping-rain-water/

* 42. 接雨水

* 时间复杂度O(n)

* 空间复杂度O(n)

*/

public class Solution {

public int trap(int[] height) {

if (height == null) {

return 0;

}

Deque<Integer> stack = new ArrayDeque<>();

int ans = 0;

for (int i = 0; i < height.length; i++) {

//如果当前值小于栈顶值,则直接push

while (!stack.isEmpty() && height[stack.peek()] < height[i]) {

//pop出来的值是比当前值小的元素

int cur = stack.pop();

System.out.println("i:" + i + " height[i]:" + height[i] + " cur:" + cur + " height[cur]:" + height[cur]);

if (stack.isEmpty()) {

break;

}

//距离差

int dis = i - stack.peek() - 1;

//面积

int h = Math.min(height[stack.peek()], height[i]) - height[cur];

ans += h * dis;

}

//当前值小于等于栈顶值

stack.push(i);

}

return ans;

}

public static void main(String[] args) {

Solution solution = new Solution();

// int[] array = new int[]{2, 1, 2, 4, 3};

// solution.test1(array);

// solution.test2(array);

//6

// System.out.println(solution.trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));

// 1

System.out.println(solution.trap(new int[]{4, 2, 3}));

}

//https://labuladong.gitbook.io/algo/shu-ju-jie-gou-xi-lie/dan-tiao-zhan

public void test1(int[] array) {

//存放结果数组

int[] tempArray = new int[array.length];

Deque<Integer> stack = new ArrayDeque<>();

for (int i = array.length - 1; i >= 0; i--) {

//判定大小

while (!stack.isEmpty() && stack.peek() <= array[i]) {

//小的直接pop丢弃

stack.pop();

}

tempArray[i] = stack.isEmpty() ? -1 : stack.peek();

System.out.println(tempArray[i]);

stack.push(array[i]);

}

System.out.println(Arrays.toString(tempArray));

}

public void test2(int[] array) {

//存放结果数组

int[] tempArray = new int[array.length];

Deque<Integer> stack = new ArrayDeque<>();

for (int i = 0; i < array.length; i++) {

//判定大小

while (!stack.isEmpty() && stack.peek() <= array[i]) {

//小的直接pop丢弃

stack.pop();

// System.out.println(pop);

}

tempArray[i] = stack.isEmpty() ? -1 : stack.peek();

System.out.println(tempArray[i]);

stack.push(array[i]);

}

System.out.println(Arrays.toString(tempArray));

}

}