# Largest Rectangle in Histogram

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

## Looks like Trapping Rain Water

```
[2, 1, 5, 6, 2, 3]
+---+
| |
+---+---+
| | |
+---+---+
| | |
+---+---+ +---+
| | | | |
+---+ +---+---+---+---+
| | | | | | |
+---+---+---+---+---+---+
| | | | | | |
+---+---+---+---+---+---+
2 1 5 6 2 3 [ Height ]
0 1 2 3 4 5 [ Index ]
```

Loop invariant with Stack/Queue

In this case, we store the bars in non-descending order. If any new bar breaks the order, we are sure that the heights of rectangles formed by the non-descending order bars have nothing to do with the new bar.

In another words, we can now count the rectangles' area and update the max.

Then, pack all saved bar into a dwarf but long one. Imagine that there would be a dwarf but long one which could win the max rectangle prize.

e.g.

```
[5, 6, 2, 3]
+---+
| |
+---+---+
| | |
+---+---+
| | |
+---+---+ +---+
| | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
0 1 2 3 [ Index ]
```

No matter what the height the bar `3`

is, rectangles formed by bar `0..3`

can not benefit form the height of bar `3`

.

Meanwhile, It is time to calculate the rectangles' area formed bar `0..2`

.

## Animation

a `bar`

is like

```
Bar { height, width }
```

new bar's height is `2`

put it into storage

```
Storage:
[{height=2, width=1}]
+---+
| |
+---+
| |
+---+
```

new bar's height is `1`

, less than `2`

, so count rectangles now.

```
+---+
| |
+---+---+
| | |
+---+---+
0 1 [Index]
```

2 rectangles formed by bar `0..1`

, the max area is `2`

Then, pack those bars into one.

```
Storage:
[{height=1, width=2}]
+-------+
| |
+-------+
0 [ Index ]
```

new bars with height `5`

and `6`

```
Storage:
[{height=1, width=2}, {height=5, width=1}, {height=5, width=1}]
+---+
| |
+---+---+
| | |
+---+---+
| | |
+---+---+
| | |
+---+---+
| | |
+-------+---+---+
| | | |
+-------+---+---+
0 1 2 [ Index ]
```

new bar with height `2`

, it is time to update max.

```
Storage:
[{height=1, width=2}, {height=5, width=1}, {height=5, width=1}]
+---+
| |
+---+---+
| | |
+---+---+
| | |
+---+---+
| | |
+---+---+---+
| | | |
+-------+---+---+---+
| | | | |
+-------+---+---+---+
0 1 2 3 [ Index ]
```

rectangles are `6 * 1`

, `5 * 2`

, `1 * 4`

.

Pack them again.

```
Storage:
[{height=1, width=2}, {height=2, width=3}]
+-----------+
| |
+-------+-----------+
| | |
+-------+-----------+
0 1 [ Index ]
```

new bar with height `3`

```
Storage:
[{height=1, width=2}, {height=2, width=3}, {height=3, width=1}]
+---+
| |
+-----------+---+
| | |
+-------+-----------+---+
| | | |
+-------+-----------+---+
0 1 2 [ Index ]
```

### Deal with left-overs

Fire another area calculating is ok.
But, a more elegant method is that you can add a fake bar with height `0`

.

`Simple is better than complex. -- Zen of Python`

### Source code *Read on Github*

```
1 public class Solution {
2
3 static class Rect {
4 int width = 1;
5 int height;
6
7 Rect(int height){
8 this.height = height;
9 }
10 }
11
12 public int largestRectangleArea(int[] height) {
13
14 if(height.length == 0) return 0;
15
16 height = Arrays.copyOf(height, height.length + 1);
17 height[height.length - 1] = 0;
18
19 Deque<Rect> stack = new LinkedList<Rect>();
20
21 stack.push(new Rect(height[0]));
22
23 int max = 0;
24
25 next:
26 for(int i = 1; i < height.length; i++){
27 int h = height[i];
28
29 Rect r = new Rect(h);
30
31 int sl = 0;
32 while(true){
33
34 if(stack.isEmpty() || h > stack.peek().height){
35 stack.push(r);
36 continue next;
37 }
38
39
40 Rect left = stack.pop();
41
42 sl += left.width;
43 max = Math.max(max, left.height * sl);
44
45 r.width = 1 + sl ; // merge left into new
46 }
47
48 }
49
50 return max;
51 }
52 }
```