85. Maximal Rectangle
You're given a binary matrix grid with rows rows and cols columns; every cell holds the character '0' or '1'. Return the area of the largest rectangle that contains only '1' cells. The rectangle's sides must be aligned with the grid, and its area is just the count of cells inside it.
If the grid contains no '1' at all, the answer is 0.
This is the two-dimensional big sibling of Largest Rectangle in Histogram — and that is more than a family resemblance.
Example 1:
Input: grid = ["10100", "10111", "11111", "10010"]
Output: 6
Explanation: The 2×3 block covering rows 1–2, columns 2–4 is all 1s and has area 6; no all-ones rectangle in this grid is bigger.
Example 2:
Input: grid = ["01", "11"]
Output: 2
Explanation: The three 1s form an L, which is not a rectangle. The best rectangles are the bottom row or the right column, each of area 2.
Constraints:
- 1 ≤ rows, cols ≤ 200
- grid[r][c] is '0' or '1'
Hints:
Fix a bottom row for the rectangle. Above every column c, count how many consecutive 1s end at that row — that column is now a histogram bar of that height.
With those heights, 'largest all-ones rectangle with its base on this row' is exactly *Largest Rectangle in Histogram*. Solve that subproblem once per row and keep the best.
The heights update in O(1) per cell as you move down one row: `h[c] = h[c] + 1` if grid[r][c] is '1', else `h[c] = 0`. With an O(cols) monotonic-stack histogram pass per row, the total is O(rows × cols).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: grid = ["10100", "10111", "11111", "10010"]
Expected output: 6