［Copy questions]

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

Example:

Input: [ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ] Output: 6

[The act of violence:

Time analysis:

Spatial analysis:

[After optimization]:

Time analysis:

Spatial analysis:

［Exotic flower condition:

［Exotic flower corner case]

The second is the matrix: 2 0,OneA null

［Thinking problem]

［Why not use other data structures or algorithms in English data structures or algorithms?

stack：The length of the longest column number is temporarily stored, and then taken out for comparison of the area.

［A word of thought]

The new h[i] is longer than the old h[i]To be able to enter is equal to the same.

With the increase of I,Old h[i] is longer than new h[i]Use of comparative area

［Input: Empty: normal condition: extra large: extra small: special case handled in the program: abnormal condition (illegal and unreasonable input):

［Drawing]

［A brush]

- h[]The array represents the vertical length, and the index in it should betransverseCoordinate cLen. Open up a list andinitialTurn to 0, used before the elements in POP stack

［Two brush]

［Three brush]

［Four brush]

［Five brush]

[Five minutes of naked eye debug results]:

［Summary:

stackOnly the most before and nowLongestA

［Complexity]: Time complexity: O (n^2) Space complexity: O(n)

［Algorithm thought: recursion / partition / greedy:

［Key template code]

［Other solutions]

dp is 2 hard

［Follow Up］：

［LCThe subject changes and changes are given.

84 histogram

[Code style]:

class Solution { public int maximalRectangle(char[][] matrix) { //cc if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0; //ini: cLen, rLen, Stack : for longest index, h[rLen + 1] int rLen = matrix.length, cLen = matrix[0].length, max = 0; int[] h = new int[cLen + 1]; h[cLen] = 0; //for loop: row (new stack) * col < cLen + 1 for (int row = 0; row < rLen; row++) { Stack<Integer> stack = new Stack<Integer>(); for (int i = 0; i < cLen + 1; i++) { //store h[i] if (i < cLen) if (matrix[row][i] == '1') h[i] += 1; else h[i] = 0; //store i, compare area, add i to stack again if (stack.isEmpty() || h[i] >= h[stack.peek()]) //New is more than old. stack.push(i); else { while (!stack.isEmpty() && h[i] < h[stack.peek()]) {//The old is compared to the new length. int top = stack.pop(); int area = h[top] * (stack.isEmpty() ? i : i - stack.peek() - 1); max = Math.max(max, area); } stack.push(i); } } } return max; } }

View Code