Avoid boundary check!


  • 0
    K

    If you are some one like me who absolutely hate dealing with corner cases.
    Below are the implementations I came up with based on top voted solutions.
    https://discuss.leetcode.com/topic/3913/my-concise-c-solution-ac-90-ms/12?page=1
    Solution 1: create a new height array (this is not the most cost efficient way though)

    	public int largestRectangleArea(int[] height) {
    		Stack<Integer> s = new Stack<Integer>();
    		int maxArea = 0;
    		int[] newHeight = new int[height.length + 2];
    		for (int i = 0; i < height.length; i++) {
    			newHeight[i + 1] = height[i];
    		}
    		s.push(0);
    		for (int i = 1; i < newHeight.length; i++) {
    			while (newHeight[i] < newHeight[s.peek()]) {
    				int h = newHeight[s.pop()];
    				maxArea = Math.max(maxArea, h * (i - s.peek() - 1));
    			}
    			s.push(i);
    		}
    		return maxArea;
    	}
    

    OR Solution 2, use another method to hide the ugly truth

    	private int[] lHeight;
    
    	public int largestRectangleArea(int[] height) {
    		Stack<Integer> s = new Stack<Integer>();
    		int maxArea = 0;
    		s.push(-1);
    		lHeight = height;
    		for (int i = 0; i <= height.length; i++) {
    			while (getHeight(i) < getHeight(s.peek())) {
    				int h = height[s.pop()];
    				int left = s.peek();
    				maxArea = Math.max(maxArea, h * (i - left - 1));
    			}
    			s.push(i);
    		}
    		return maxArea;
    	}
    
    	public int getHeight(int i) {
    		if (i < 0 || i >= lHeight.length) return 0;
    		else return lHeight[i];
    	}
    

Log in to reply
 

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