16 lines Java O(n) solution


  • 1
    J
    public class Solution {
        public int largestRectangleArea(int[] heights) {
            if (heights == null || heights.length == 0) return 0;
            Deque<Integer> stack = new LinkedList<>();
            int i = 0, res = 0;
            while (i < heights.length || !stack.isEmpty()) {
                if (i == heights.length || (!stack.isEmpty() && heights[stack.peek()] > heights[i])) {
                    int h = heights[stack.pop()];
                    int left = stack.isEmpty()? 0 : stack.peek() + 1;
                    res = Math.max(res, h * (i - left));
                }
                else stack.push(i++);
            }
            return res;
        }
    }

Log in to reply
 

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