算法题之接雨水

解题思路，通过栈，但是需要正向栈和逆向栈进行俩次叠加，需要对最大值公共部分进行特殊处理

public int trap(int[] height) {

        int maxHeight = 0;

        int indexOrderValue = 0, indexInvertedOrderValue = 0, orderNum = 0, invertedOrderNum = 0;

        Stack<Map<String, Integer>> orderStack = new Stack<Map<String, Integer>>();

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

            if (height[i] >= indexOrderValue) {

                HashMap<String, Integer> map = new HashMap<String, Integer>();

                map.put("index", i);

                map.put("value", height[i]);

                orderStack.push(map);

                orderNum++;

                indexOrderValue = height[i];

            }

        }

        Stack<Map<String, Integer>> indexInvertedOrderStack = new Stack<Map<String, Integer>>();

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

            if (height[i] >= indexInvertedOrderValue) {

                HashMap<String, Integer> map = new HashMap<String, Integer>();

                map.put("index", i);

                map.put("value", height[i]);

                indexInvertedOrderStack.push(map);

                invertedOrderNum++;

                indexInvertedOrderValue = height[i];

            }

        }

        //正序的栈计算左边的水深度，逆序的栈算右边水的深度，如果存在最大值相等情况，逆序时不计算其最大值的深度

        Integer preIndex = 0, preValue = 0, repetitionNum = 0, orderMaxValue = 0;

        for (int i = 0; i < orderNum; i++) {

            HashMap<String, Integer> map = (HashMap<String, Integer>) orderStack.pop();

            Integer index = map.get("index");

            Integer value = map.get("value");

            //计算到最后一个的

            if (i == 0) {

                orderMaxValue = value;

            } else {

                //计算最大值重复次数

                if (orderMaxValue == value) {

                    repetitionNum++;

                }

                int boundary = 0;

                //计算边界值

                if (preValue == value) {

                    boundary = preValue;

                } else {//此处只可能是小于

                    boundary = value;

                }

                //正序，所以index<preIndex

                for (int temIndex = index + 1; temIndex < preIndex; temIndex++) {

                    maxHeight += boundary - height[temIndex];

                }

            }

            preIndex = index;

            preValue = value;

        }

        //重新初始化其值

        preIndex = 0;

        preValue = 0;

        //逆序计算右边水位高度

        for (int i = 0; i < invertedOrderNum; i++) {

            HashMap<String, Integer> map = (HashMap<String, Integer>) indexInvertedOrderStack.pop();

            Integer index = map.get("index");

            Integer value = map.get("value");

            if (i > 0) {

                //如果最大值有相等情况，在正序中已经计算累加，逆序直接跳过该计算

                if (repetitionNum > 0) {

                    repetitionNum--;

                    preIndex = index;

                    preValue = value;

                    continue;

                } else {

                    int boundary = 0;

                    //计算边界值

                    if (preValue == value) {

                        boundary = preValue;

                    } else {//此处只可能是小于

                        boundary = value;

                    }

                    //倒序，所以 preIndex<index

                    for (int temIndex = preIndex + 1; temIndex < index; temIndex++) {

                        maxHeight += boundary - height[temIndex];

                    }

                }

            }

            preIndex = index;

            preValue = value;

        }

        return maxHeight;

    }

}