Largest Rectangle in Histogram LeetCode solution in Java

1
class Solution {
2
  public int largestRectangleArea(int[] heights) {
3
    Stack<Integer> stack1 = new Stack<>();
4
    Stack<Integer> stack2 = new Stack<>();
5
    int n = heights.length;
6
    int[] left = new int[n];
7
    int[] right = new int[n];
8
    int[] width = new int[n];
9

10
    for (int i = 0; i < n; i++) {
11
      while (!stack1.isEmpty() && heights[stack1.peek()] >= heights[i]) stack1.pop();
12
      if (!stack1.isEmpty()) left[i] = stack1.peek();
13
      else left[i] = -1;
14
      stack1.push(i);
15
    }
16

17
    for (int i = n - 1; i >= 0; i--) {
18
      while (!stack2.isEmpty() && heights[stack2.peek()] >= heights[i]) stack2.pop();
19
      if (!stack2.isEmpty()) right[i] = stack2.peek();
20
      else right[i] = n;
21
      stack2.push(i);
22
    }
23

24
    for (int i = 0; i < n; i++) {
25
      width[i] = right[i] - left[i] - 1;
26
    }
27
    int mxArea = 0;
28
    for (int i = 0; i < n; i++) {
29
      mxArea = Math.max(mxArea, width[i] * heights[i]);
30
    }
31
    return mxArea;
32
  }
33
}