Problems-Solving/Java/MaximalRectangle.java at develop · hienmv/Problems-Solving · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
// https://leetcode.com/problems/maximal-rectangle/
// #array #hash-table #dynamic-programming #stack #todo
/*
[
    ["0","1","1","0","1"],
    ["1","1","0","1","0"],
    ["0","1","1","1","0"],
    ["1","1","1","1","0"],
    ["1","1","1","1","1"],
    ["0","0","0","0","0"]
]

*/
/*
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]

dpY: [
  [1, 0, 1, 0, 0]
  [2, 0, 2, 1, 1]
  [3, 1, 3, 2, 2]
  [4, 0, 0, 3, 0]
]

 3, 1, 3, 2, 2

*/
/*
   _   _
  | | | |___
  | |_| | | |
  | | | | | |

0 * 1 * * 2

0 1 1 2

/* todo ? leetcode.com/problems/largest-rectangle-in-histogram/ */
/*
- nhieu bien
-> thu co dinh tung bien.
*/
class Solution {
  public int largestRectangleArea(int[] heights, int n) {
    int result = 0;
    Stack<Integer> st = new Stack<>();
    st.push(0);
    for (int i = 1; i <= n; i++) {
      while (!st.isEmpty() && heights[st.peek()] >= heights[i]) {
        st.pop();
      }
      int prev = st.isEmpty() ? 0 : st.peek();
      result = Math.max(result, heights[i] * (i - prev));
      st.push(i);
    }

    while (!st.isEmpty()) {
      int idx = st.pop();
      int prev = st.isEmpty() ? 0 : st.peek();
      result = Math.max(result, heights[idx] * (n - prev));
    }

    return result;
  }

  // fixed one dimension => [x, 1] || [1, y]
  public int maximalRectangle(char[][] matrix) {
    int m = matrix.length;
    if (m == 0) return 0;
    int n = matrix[0].length;

    int[] dp = new int[n + 1];
    int result = 0;
    for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
        if (matrix[i - 1][j - 1] == '1') {
          dp[j] += 1;
        } else {
          dp[j] = 0;
        }
      }
      result = Math.max(result, largestRectangleArea(dp, n));
    }
    return result;
  }
}