My accepted java solution , this "hard" problem seems to be easier than it's rated


  • 0
    T

    basically u have to keep a stack, and whenever there is a "| " shape you need to check the top 2 levels of stack and see if u have a "||" shape, then count the area by horizontal layers.

    public class Solution {
    static class Block {
        public int h;
        public int x;
        public Block(int x, int h) {
            this.x = x;
            this.h = h;
        }
    }
    Stack<Block> lastLeft = new Stack<Block>();
    public int trap(int[] A) {
        int area = 0;
        lastLeft.clear();
        for(int i=0;i<A.length;i++) {
            while(!lastLeft.empty()) {
            Block bottom = lastLeft.peek();
            if (bottom.h < A[i]) {// bottom
                bottom = lastLeft.pop();
                if (lastLeft.empty()) break;
                Block left = lastLeft.peek();
                                area += (i - left.x -1 )* (Math.min(left.h, A[i]) - bottom.h);
    
    
            } else break;
            
            }
                        lastLeft.push(new Block(i, A[i]));
    
        }
        
        return area;
        
    }
    

    }


Log in to reply
 

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