Accepted Java Solution


  • 0
    W

    I am not quite good at writing short code.. Here's a long solution that express my idea of algorithm.
    It's like the Stack solution given. O(n) time and O(m) space, single pass. m is the longest decending sequence (sorta).
    The idea is to "merge" a block to the left and collect water as soon as possible.
    So when it's always decending, you cannot be sure water can be collected, have to keep it in stack memory. Once a upward move is detected,
    you decide how to merge it and collect the water, after that, you always end up a decending sequence of blocks.
    When block is merged, the width can grow to larger than 1. (Think as if the water whole is filled)

    import java.util.ArrayList;
    import java.util.List;
    
    class Solution {
        static class Block {
            int h;
            int w;
            int at;
            Block(int h, int w, int at) {
                this.h = h;
                this.w = w;
                this.at = at;
            }
        }
        public int trap(int[] height) {
            if (height.length == 0) {
                return 0;
            }
    
            List<Block> q = new ArrayList<>();
            q.add(new Block(height[0], 1, 0 ));
    
            int water = 0;
    
            for (int i = 1; i < height.length; i++) {
                int end = q.size() - 1;
                while (true) {
                    int h = q.get(end).h;
    
                    if (height[i] < h) {
                        q.add(new Block(height[i], 1, i));
                    } else if (end == 0) {
                        q.remove(end);
                        q.add(new Block(height[i], 1, i));
                    } else {
                        if (height[i] == h) {
                            q.get(end).w += 1;
                        } else {
                            int pre = end - 1;
                            if (height[i] < q.get(pre).h) {
                                water += (height[i] - q.get(end).h) * q.get(end).w;
                                q.get(end).w += 1;
                                q.get(end).h = height[i];
                            } else if (height[i] == q.get(pre).h) {
                                water += (height[i] - q.get(end).h) * q.get(end).w;
                                q.get(pre).w += q.get(end).w + 1;
                                q.remove(end);
                            } else {
                                water += (q.get(pre).h - q.get(end).h) * q.get(end).w;
                                q.get(pre).w += q.get(end).w;
                                q.remove(end);
                                --end;
                                continue;
                            }
                        }
                    }
                    break;
                }
            }
    
            return water;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.