FilesExpand file tree

 master

/

MaximalRectangle.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

99 lines (89 loc) · 2.56 KB

 master

/

MaximalRectangle.java

Copy path

Top

File metadata and controls

• Code
• Blame

99 lines (89 loc) · 2.56 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

91

92

93

94

95

96

97

98

99

/**

* Practiced on 12/9/2012

*

* Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle

* containing all ones and return its area.

*

* =============================

* The idea is not easy to think of.

*

* 1. Suppose we have given matrix

* 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

* 2. Build the count matrix, which calculates how many 1's each 1 has above:

* 0 1 1 0 1

* 1 2 0 1 0

* 0 3 1 2 0

* 1 4 2 3 0

* 2 5 3 4 1

* 3. Then, for each row of count matrix, treat it as a histogram, and find the maximum area

* given by the histogram.

* 4. Find the maximum of the maximum area found by each row.

*/

package com.congli.leetcode;

import java.util.Stack;

public class MaximalRectangle {

public int maximalRectangle(char[][] matrix)

{

if(matrix == null || matrix.length==0) return 0;

int[] count1 = new int[matrix[0].length];

for(int j = 0; j < matrix[0].length; ++j)

count1[j] = matrix[0][j] - '0';

int result = 0;

for(int i = 1; i < matrix.length; ++i)

{

result = Math.max(result, processRow(count1));

int[] count2 = new int[matrix[0].length];

for(int j = 0; j < matrix[0].length; ++j)

count2[j] = matrix[i][j] == '0' ? 0 : count1[j]+1;

count1 = count2;

}

result = Math.max(result, processRow(count1));

return result;

}

private int processRow(int[] array)

{

Stack<Integer> stack = new Stack<Integer>();

int[] lengthToRight = new int[array.length];

stack.push(0);

for(int i = 1; i < array.length; ++i)

{

while(!stack.isEmpty() && array[stack.peek()] > array[i])

{

lengthToRight[stack.peek()] = i-stack.peek();

stack.pop();

}

stack.push(i);

}

while(!stack.isEmpty())

{

lengthToRight[stack.peek()] = array.length-stack.peek();

stack.pop();

}

int[] lengthToLeft = new int[array.length];

stack.push(array.length-1);

for(int i = array.length-2; i >= 0; --i)

{

while(!stack.isEmpty() && array[stack.peek()] > array[i])

{

lengthToLeft[stack.peek()] = stack.peek()-i-1;

stack.pop();

}

stack.push(i);

}

while(!stack.isEmpty())

{

lengthToLeft[stack.peek()] = stack.peek();

stack.pop();

}

int result = 0;

for(int i = 0; i < array.length; ++i)

{

result = Math.max(result, array[i]*(lengthToLeft[i]+lengthToRight[i]));

}

return result;

}

}