面试经典 150 题 （十七）

思路:1、先将下标和高度放入HashMap中，防止排序之后破坏高度和下标的映射关系
2、将HashMap转成Map.Entry的列表并且重写Collections.sort中的sort方法实现将数组按照键值对的值从大到小排序。
3、设置flag数组用于标识那些高度区间没有被访问过
4、从排序好的数组中取出高度，再向两侧遍历。

class Solution {
    public int trap(int[] height) {
        int trap = 0;
        HashMap<Integer, Integer> mapping = new HashMap<Integer, Integer>();
        int length = height.length;
        boolean[] flag = new boolean[length];
        for (int i = 0; i < length; i++){
            flag[i] = false;
            //将高度和下标存进map中
            mapping.put(i, height[i]);
        }
        List<Map.Entry<Integer, Integer>> entryList = new ArrayList<Map.Entry<Integer, Integer>>(mapping.entrySet());
        Collections.sort(entryList, new Comparator<Map.Entry<Integer, Integer>>(){
            @Override
            public int compare(Map.Entry<Integer, Integer> entry1, Map.Entry<Integer, Integer> entry2){
                return entry2.getValue().compareTo(entry1.getValue());
            }
        });
        int i = 0;
        for (Map.Entry<Integer, Integer> entry : entryList){
            flag[entry.getKey()] = true;
            //向左搜寻
            i = entry.getKey() - 1;
            while(i >= 0 && flag[i] == false){
                i--;
            }
            if (i >= 0 && flag[i] == true){
                for (int j = i + 1; j < entry.getKey(); j++){
                    trap = trap +  height[entry.getKey()] - height[j];
                    flag[j] = true;
                }
            }
            //向右搜寻
            i = entry.getKey() + 1;
            while(i <= length - 1 && flag[i] == false){
                i++;
            }
            if (i <= length - 1 && flag[i] == true){
                for (int j = i - 1; j > entry.getKey(); j--){
                    trap += height[entry.getKey()] - height[j];
                    flag[j] = true;
                }
            }
        }
        return trap;
    }
}