My Java AC solution, O(n)


  • 0
    D
    public class Solution {
        public int largestRectangleArea(int[] heights) {
            Stack<Integer> s = new Stack<>();
    	    int res = 0;
    	    for (int i = 0; i<heights.length; ++i) {
    		    if (s.isEmpty() || heights[s.peek()] < heights[i]) {
    			    s.push(i);
                } else {
    	            while (!s.isEmpty() && heights[s.peek()] >= heights[i]) {
    		            res = Math.max(res, updateArea(s, heights, i));
                    }
                    s.push(i);
                }
            }
            while (!s.isEmpty()) {
    	        res = Math.max(res, updateArea(s, heights, heights.length));
            }
            return res;
        }
        
        int updateArea(Stack<Integer> s, int[] heights, int i) {
    	    int cur = s.pop();
            int curHeight = heights[cur];
            int curWidth = s.isEmpty()?i:(i-s.peek()-1);
            return curHeight*curWidth;
        }
    }
    

Log in to reply
 

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