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}