Maximal Rectangle [C++]
IntuitionTo solve the problem of finding the maximal rectangle in a binary matrix, we can leverage the concept of histogram area calculation. The idea is to tre
# Intuition
To solve the problem of finding the maximal rectangle in a binary matrix, we can leverage the concept of histogram area calculation. The idea is to treat each row of the matrix as the base of a histogram and calculate the largest rectangle that can be formed under that histogram. By iterating through each row and updating the heights of the histogram based on the presence of '1's, we can find the maximal rectangle in the entire matrix.

# Approach
1. **Initialize Heights**: Start by initializing a vector `heights` with the same number of columns as the matrix, setting all values to 0. This vector will keep track of the height of the histogram at each column.

2. **Update Heights**: For each row in the matrix, update the `heights` vector. If the current cell contains '1', increment the height at that column. If it contains '0', reset the height to 0.

3. **Calculate Largest Rectangle**: After updating the heights for each row, use the `largestRectangleArea` function to calculate the largest rectangle that can be formed under the current histogram. This function uses a stack-based approach to efficiently compute the maximum area.

4. **Track Maximum Area**: Keep track of the maximum area found across all rows.

5. **Return Result**: After processing all rows, return the maximum area found.

# Complexity
- **Time Complexity**: The time complexity is \(O(n \times m)\), where \(n\) is the number of rows and \(m\) is the number of columns in the matrix. This is because we process each cell in the matrix once and for each row, we compute the largest rectangle area in \(O(m)\) time.
  
- **Space Complexity**: The space complexity is \(O(m)\), where \(m\) is the number of columns. This is due to the additional space used by the `heights` vector and the stack in the `largestRectangleArea` function.

# Code
```cpp
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty()) return 0;
        int n = matrix.size(), m = matrix[0].size();
        vector<int> heights(m, 0);
        int maxArea = 0;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0;
            }
            maxArea = max(maxArea, largestRectangleArea(heights));
        }

        return maxArea;
    }

    int largestRectangleArea(vector<int>& heights) {
        stack<int> s;
        heights.push_back(0);
        int maxArea = 0;

        for (int i = 0; i < heights.size(); ++i) {
            while (!s.empty() && heights[s.top()] > heights[i]) {
                int h = heights[s.top()];
                s.pop();
                int w = s.empty() ? i : i - s.top() - 1;
                maxArea = max(maxArea, h * w);
            }
            s.push(i);
        }

        heights.pop_back();
        return maxArea;
    }
};
```

### Explanation
- **Initialization**: We start by checking if the matrix is empty. If it is, we return 0. Otherwise, we initialize the `heights` vector to keep track of the histogram heights.
- **Updating Heights**: For each row, we update the `heights` vector based on the current cell value. If the cell is '1', we increment the height; otherwise, we reset it to 0.
- **Calculating Largest Rectangle**: The `largestRectangleArea` function calculates the largest rectangle under the histogram using a stack. It iterates through the heights, using the stack to keep track of indices and calculating the area whenever a smaller height is encountered.
- **Tracking Maximum Area**: We keep updating the `maxArea` with the largest area found for each row.
- **Returning Result**: Finally, we return the `maxArea` which holds the largest rectangle area found in the entire matrix.
['C++']