# LC 84. Largest Rectangle in Histogram

### [Problem link](https://leetcode.com/problems/largest-rectangle-in-histogram/)

###### tags: `leedcode` `python` `hard` `Monotone Stack`

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

**Example 1:**
<img alt="" src="https://assets.leetcode.com/uploads/2021/01/04/histogram.jpg" style="width: 522px; height: 242px;" />

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:**
<img alt="" src="https://assets.leetcode.com/uploads/2021/01/04/histogram-1.jpg" style="width: 202px; height: 362px;" />

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

**Constraints:**

- <code>1 <= heights.length <= 10⁵</code>
- <code>0 <= heights[i] <= 10⁴</code>

## Solution 1 - Monotone Stack

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights.append(0)
        heights.insert(0, 0)
        n = len(heights)
        stack = [0]
        res = 0

        for i in range(n):
            while stack and heights[i] < heights[stack[-1]]:
                h = heights[stack.pop()]
                w = i - stack[-1] - 1
                res = max(res, h * w)
            stack.append(i)

        return res

## Solution 2 - Monotone Stack(rev2.0)

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights.append(0)
        n = len(heights)
        stack = [-1]
        res = 0

        for i in range(n):
            while stack and heights[i] < heights[stack[-1]]:
                h = heights[stack.pop()]
                w = i - stack[-1] - 1
                res = max(res, h * w)
            stack.append(i)

        return res

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(n) |
>| Solution 2 | O(n) | O(n) |

## Note
sol1, 2:
類似於[LC 42. Trapping Rain Water](https://hackmd.io/@Alone0506/r1btGztc2) 和 [LC 739. Daily Temperatures](https://hackmd.io/@Alone0506/SyjvoGd9n)
stack的元素為monotone increasing stack. ex: [0, 2, 4, 5]

ref: [代碼隨想錄](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0084.%E6%9F%B1%E7%8A%B6%E5%9B%BE%E4%B8%AD%E6%9C%80%E5%A4%A7%E7%9A%84%E7%9F%A9%E5%BD%A2.md)