84. Largest Rectangle in Histogram#
Approach 1: Using two for loops (Time Limit Exceeded)#
1class Solution {
2
3 public int largestRectangleArea(int[] heights) {
4 int maxArea = 0;
5
6 for (int i = 0; i < heights.length; ++i) {
7 int currentMin = heights[i];
8 for (int j = i; j < heights.length; ++j) {
9 currentMin = Math.min(currentMin, heights[j]);
10 maxArea = Math.max(maxArea, currentMin * (j - i + 1));
11 }
12 }
13
14 return maxArea;
15 }
16}
Approach 2: Using two for loops with search pruning (Time Limit Exceeded)#
1class Solution {
2
3 public int largestRectangleArea(int[] heights) {
4 int maxArea = 0;
5
6 for (int i = 0; i < heights.length; ++i) {
7 if (i + 1 < heights.length && heights[i] <= heights[i + 1]) {
8 continue;
9 }
10 int currentMin = heights[i];
11 for (int j = i; j >= 0; --j) {
12 currentMin = Math.min(currentMin, heights[j]);
13 maxArea = Math.max(maxArea, currentMin * (i - j + 1));
14 }
15 }
16
17 return maxArea;
18 }
19}
Approach 3: Using Monotonic Stack (increasing)#
1class Solution {
2
3 public int largestRectangleArea(int[] heights) {
4 int maxArea = 0;
5 Stack<Integer> stk = new Stack<>();
6
7 for (int i = 0; i <= heights.length; ++i) {
8 while (
9 !stk.isEmpty() &&
10 (i == heights.length || heights[stk.peek()] > heights[i])
11 ) {
12 int height = heights[stk.pop()];
13 int width = stk.isEmpty() ? i : (i - stk.peek() - 1);
14 maxArea = Math.max(maxArea, height * width);
15 }
16
17 stk.push(i);
18 }
19
20 return maxArea;
21 }
22}