[LeetCode] 84. Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given heights = [2,1,5,6,2,3],
return 10.

Thought process:

The idea is to iterate through the array, and use a stack which contains only numbers in ascending order. As I iterate through the array, I compare height[i] with the top number on the stack:

1. If height[i] <= height[top of stack], pop off top of the stack until height[i] > height[top of the stack]. For every number popped off, the largest rectangle with height == height[number] is height[number] * (i - 1 - stack.peek()).
2. Else, push i onto stack.

Add a -1 to the end of height, so that all numbers are guaranteed to be popped off the stack.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

public class Solution { public int largestRectangleArea(int[] heights) { Stack<Integer> stack = new Stack<>(); int largest = 0; for (int i = 0; i <= heights.length; i++) { int current = i == heights.length ? -1 : heights[i]; while (!stack.isEmpty() && current <= heights[stack.peek()]) { int height = heights[stack.pop()]; int width = stack.isEmpty() ? i : i - 1 - stack.peek(); largest = Math.max(largest, height * width); } stack.push(i); } return largest; } }

Time complexity:
All numbers in heights will be visited twice no matter what heights looks like. O(n).