# Leetcode 84 - Largest rectangle in histogram

`Note:`

- For each
`col`

, we need to find the`first`

col that is`shorter`

than it on both`left`

and`right`

. - Use brute force will give us a O(n^2) algorithm. Can we finish it in just one iteration?
- Is there a data structure that can quickly give us the
`first`

col that is shorter than the current col on the`left`

and`right`

? `Monotonic queue`

!- For an element stack[i] in
`stack`

,`stack[i-1]`

is the first element shorter than stack[i] on the left. - What about
`right`

side? When we got a real shorter col and need to pop many cols including`stack[i]`

, we found the`first`

shorter col on the right. - Use
`monoStack[]`

to store indexes of cols. - How to calculate area of a rectangle?
- For example, the current stack[] is
`[1,4,7]`

, which is corresponding to heights like`[2,5,8]`

, the next col height is`6`

. - How do we know the
`WIDTH`

of col with height`8`

?- Pop up the top of stack first as
`top`

. - Clearly, the width is between cols with height 5 and 6.
- Right now the stack is like
`[1, 4]`

. - The
`width = i - stack[stack.length - 1] - 1`

, which is 3 (index 5, 6, 7). `Area = height[top] * width`

.

- Pop up the top of stack first as
`DETAILS`

:- What if the cols are strictly increasing? We don’t even have a chance to calculate the area.

`Add 0 to the end of heights[]`

!!- In this way, we can ensure that we’ve pop out all cols after all iterations.

- When there is only one element left in the
`stack`

, there is`stack[stack.length - 1]`

is`UNDEFINED`

!

`Add 0 to the start of heights[] as well`

!!

`Question:`

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 | Input: heights = [2,1,5,6,2,3] |

`Code:`

1 | /** |