Given an array of integers **A** of size **N**. **A** represents a histogram i.e **A[i]** denotes height of

the**ith** histogram’s bar. Width of each bar is **1**.

the

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.

Find the area of largest rectangle in the histogram.

The only argument given is the integer array A.

Return the area of largest rectangle in the histogram.

Input 1: A = [2, 1, 5, 6, 2, 3] Output 1: 10 Explanation 1: The largest rectangle is shown in the shaded area, which has area = 10 unit.

Method:

Maintain a stack that keeps track of the indices of elements that are increasing, when we see an element that is smaller than the top of the stack, we can start calculating the areas. The difficulty is in determining the left bound, after we pop the top of the stack, the left bound can be determined by the current top + 1, because current top is smaller or equal to the element we popped, thus current top + 1 must be greater than or equal to the element we popped.

6 2 5 4 5 (0)

for example, when we are popping 4, the previous 5 is not in the stack because it was already popped, thus the next element in the stack is 2 (index 1), so the left bound is 1 + 1 = 2

Solution:

Time: O(n)

Space: O(n)

Maintain a stack that keeps track of the indices of elements that are increasing, when we see an element that is smaller than the top of the stack, we can start calculating the areas. The difficulty is in determining the left bound, after we pop the top of the stack, the left bound can be determined by the current top + 1, because current top is smaller or equal to the element we popped, thus current top + 1 must be greater than or equal to the element we popped.

6 2 5 4 5 (0)

for example, when we are popping 4, the previous 5 is not in the stack because it was already popped, thus the next element in the stack is 2 (index 1), so the left bound is 1 + 1 = 2

Solution:

Time: O(n)

Space: O(n)

public class Solution { public int largestRectangleArea(ArrayList<Integer> A) { // 6 2 5 4 5 // index stack Deque<Integer> stack = new ArrayDeque<>(); int area = 0; A.add(0); for (int i = 0; i < A.size(); i ++) { int currentHeight = A.get(i); while (!stack.isEmpty() && A.get(stack.peekFirst()) > currentHeight) { int height = A.get(stack.pop()); int left = stack.isEmpty() ? 0 : stack.peekFirst() + 1; int width = i - left; area = Math.max(area, width * height); } stack.push(i); } return area; } }