Maximal Rectangle LeetCode solution in Java

1
class Solution {
2
  public int maximalRectangle(char[][] matrix) {
3
    ArrayList<Integer> list = new ArrayList<>();
4
    int n = matrix[0].length;
5
    for (int i = 0; i < n; i++) {
6
      list.add(Character.getNumericValue(matrix[0][i]));
7
    }
8

9
    int maxArea = maximumArea(list);
10
    int m = matrix.length;
11

12
    for (int i = 1; i < m; i++) {
13
      for (int j = 0; j < n; j++) {
14
        if (matrix[i][j] == '1') {
15
          list.set(j, Character.getNumericValue(matrix[i][j]) + list.get(j));
16
        } else list.set(j, 0);
17
      }
18
      maxArea = Math.max(maxArea, maximumArea(list));
19
    }
20
    return maxArea;
21
  }
22

23
  public int maximumArea(ArrayList<Integer> heights) {
24
    Stack<Integer> stack1 = new Stack<>();
25
    Stack<Integer> stack2 = new Stack<>();
26
    int n = heights.size();
27
    int[] left = new int[n];
28
    int[] right = new int[n];
29
    int[] width = new int[n];
30

31
    for (int i = 0; i < n; i++) {
32
      while (!stack1.isEmpty() && heights.get(stack1.peek()) >= heights.get(i)) stack1.pop();
33
      if (!stack1.isEmpty()) left[i] = stack1.peek();
34
      else left[i] = -1;
35
      stack1.push(i);
36
    }
37

38
    for (int i = n - 1; i >= 0; i--) {
39
      while (!stack2.isEmpty() && heights.get(stack2.peek()) >= heights.get(i)) stack2.pop();
40
      if (!stack2.isEmpty()) right[i] = stack2.peek();
41
      else right[i] = n;
42
      stack2.push(i);
43
    }
44

45
    for (int i = 0; i < n; i++) {
46
      width[i] = right[i] - left[i] - 1;
47
    }
48
    int mxArea = 0;
49
    for (int i = 0; i < n; i++) {
50
      mxArea = Math.max(mxArea, width[i] * heights.get(i));
51
    }
52
    return mxArea;
53
  }
54
}