# 0084. Largest Rectangle in Histogram

<https://leetcode.com/problems/largest-rectangle-in-histogram>

## Description

Given an array of integers `heights` representing the histogram's bar height where the width of each bar is `1`, return *the area of the largest rectangle in the histogram*.

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/01/04/histogram.jpg)

```
**Input:** heights = [2,1,5,6,2,3]
**Output:** 10
**Explanation:** The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2021/01/04/histogram-1.jpg)

```
**Input:** heights = [2,4]
**Output:** 4
```

**Constraints:**

* `1 <= heights.length <= 105`
* `0 <= heights[i] <= 104`

## ac1: stack

stack & array push -1 at first, like #32 push 0 at last, like this one #84

```java
class Solution {
    public int largestRectangleArea(int[] heights) {
        // edge cases
        if (heights.length == 0) return 0;

        int max = 0;
        // stack iterate
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(-1);
        for (int i = 0; i <= heights.length; i++) {
            int currh = i == heights.length ? 0 : heights[i];
            while (stack.peek() != -1 && currh < heights[stack.peek()]) {
                int h = heights[stack.pop()];
                int w = i - stack.peek() - 1;
                max = Math.max(max, h * w);
            }
            stack.push(i);
        }

        return max;
    }
}

/*
stack
push -1 at first, like #32
push 0 at last, like this one #84

if stack.isEmpty() -> stack.peek() != -1 || heights[i] >= height[stack.peek()], push
while height[i] < height[stack.peek()], h = height[stack.pop()], w = i - stack.peek() - 1

*/
```

This is more intuitive without pushing -1 or 0:

```java
class Solution {
    public int largestRectangleArea(int[] heights) {
        // edge cases
        if (heights.length == 0) return 0;
        
        int len = heights.length;
        int max = 0;
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                int h = heights[stack.pop()];
                int w = stack.isEmpty() ? i : i - stack.peek() - 1;
                max = Math.max(max, h * w);
            }
            stack.push(i);
        }
        
        while (!stack.isEmpty()) {
            int h = heights[stack.pop()];
            int w = stack.isEmpty() ? len : len - stack.peek() - 1;
            max = Math.max(max, h * w);
        }
        
        return max;
    }
}
```