# LeetCode 84. Largest Rectangle in Histogram 直方图最大矩形覆盖

## 题目

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

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. 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.

Example:

```Input: [2,1,5,6,2,3]
Output: 10```

## Java代码

```class Solution {
public int largestRectangleArea(int[] heights) {
if (heights == null || heights.length == 0) {
return 0;
}

int maxArea = 0;
Stack<Integer> stack = new Stack<>();
stack.push(-1);

for (int i = 0; i < heights.length; i++) {
int currentBarHeight = heights[i];

while (stack.peek() != -1 && currentBarHeight <= heights[stack.peek()]) {
int height = heights[stack.pop()];
int width = i - stack.peek() - 1;

int area = height * width;
maxArea = Math.max(area, maxArea);
}

stack.push(i);
}

while (stack.peek() != -1) {
int height = heights[stack.pop()];
int width = heights.length - stack.peek() - 1;

int area = height * width;
maxArea = Math.max(area, maxArea);
}

return maxArea;

// Time complexity : O(n). n numbers are pushed and popped.
// Space complexity : O(n). Stack is used.
}
}```