Problem

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given[0,1,0,2,1,0,1,3,2,1,2,1], return6.

思路一(heap)

• for ith bar, we need to find the highest bar on its left and right
• then get MIn(left, right), and add to res
• so use two heap, left and right
• time complexity: O(n^2), because heap's remove operation takes O(n) time
• space complexity: O(n)

    public int trap(int[] height) {
        if (height == null || height.length <= 2) {
            return 0;
        }
        int res = 0;
        int len = height.length;
        Bar[] bars = new Bar[len];
        for (int i = 0; i < len; i++) {
            bars[i] = new Bar(i, height[i]);
        }
        PriorityQueue<Bar> left = new PriorityQueue<>(len, (Bar b1, Bar b2) -> b2.height - b1.height);
        PriorityQueue<Bar> right = new PriorityQueue<>(len, left.comparator());

        for (int i = len - 1; i >= 2; i--) {
            right.offer(bars[i]);
        } 
        left.offer(bars[0]);
        for (int i = 1; i < len - 1; i++) {
            Bar cur = bars[i];
            // System.out.println("left : " + left.peek().height);
            // System.out.println("right : " + right.peek().height);
            if (left.peek().height > cur.height && right.peek().height > cur.height) {
                // System.out.println("hello");
                res += Math.min(left.peek().height, right.peek().height) - cur.height;
            }
            left.offer(cur);
            right.remove(bars[i + 1]);
        }
        return res;
    }

    class Bar {
        int index;
        int height;
        public Bar(int i, int h) {
            index = i;
            height = h;
        }
    }

优化(TreeSet)

• treeset's remove takes O(logn)
• one thing needs to be notice is that the comparator should be modified, because its equals() function depends on it. if heights are the same, the set just keeps one.
• time complexity: O(nlogn)

    public int trap(int[] height) {
        if (height == null || height.length <= 2) {
            return 0;
        }
        int res = 0;
        int len = height.length;
        Bar[] bars = new Bar[len];
        for (int i = 0; i < len; i++) {
            bars[i] = new Bar(i, height[i]);
        }
        TreeSet<Bar> left = new TreeSet<>(new Comparator<Bar>(){
            public int compare(Bar b1, Bar b2) {
                if (b2.height - b1.height == 0) {
                    return b1.index - b2.index;
                }
                return b2.height - b1.height;
            }
        });
        TreeSet<Bar> right = new TreeSet<>(left.comparator());

        for (int i = len - 1; i >= 2; i--) {
            right.add(bars[i]);
        } 
        // System.out.println(right.size());
        left.add(bars[0]);
        for (int i = 1; i < len - 1; i++) {
            Bar cur = bars[i];

            int l = left.first().height;
            int r = right.first().height;
            if (l > cur.height && r > cur.height) {
                res += Math.min(l, r) - cur.height;
            }
            left.add(cur);
            right.remove(bars[i + 1]);
        }
        return res;
    }

    class Bar {
        int index;
        int height;
        public Bar(int i, int h) {
            index = i;
            height = h;
        }
    }