<p>Given a <code>rows x cols</code>&nbsp;binary <code>matrix</code> filled with <code>0</code>&#39;s and <code>1</code>&#39;s, find the largest rectangle containing only <code>1</code>&#39;s and return <em>its area</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/14/maximal.jpg" style="width: 402px; height: 322px;" />
<pre>
<strong>Input:</strong> matrix = [[&quot;1&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;],[&quot;1&quot;,&quot;0&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;],[&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;],[&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;]]
<strong>Output:</strong> 6
<strong>Explanation:</strong> The maximal rectangle is shown in the above picture.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> matrix = [[&quot;0&quot;]]
<strong>Output:</strong> 0
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> matrix = [[&quot;1&quot;]]
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>rows == matrix.length</code></li>
	<li><code>cols == matrix[i].length</code></li>
	<li><code>1 &lt;= row, cols &lt;= 200</code></li>
	<li><code>matrix[i][j]</code> is <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
</ul>

class Solution {
public:
vector<int>v;
int MAH(vector<int> &v){
    
vector<int> right;
vector<int> left;
stack<pair<int,int>> s;
// Step 1: Calculate 'right' array (nearest smaller element to the right)
        for(int j = v.size() - 1; j>= 0; j--) {
            while (!s.empty() && s.top().first > v[j]) {
                s.pop();
            }
            if (s.empty()) {
                right.push_back(v.size());
            } else {
                right.push_back(s.top().second);
            }
            s.push({v[j], j});
        }
        reverse(right.begin(), right.end());
        
        // Clear stack for reuse
        while (!s.empty()) {
            s.pop();
        }
        
// Step 2: Calculate 'left' array (nearest smaller element to the left)
        for(int j = 0; j <v.size(); j++) {
            while (!s.empty() && s.top().first >=v[j]) {
                s.pop();
            }
            if (s.empty()) {
                left.push_back(-1);
            } else {
                left.push_back(s.top().second);
            }
            s.push({v[j], j});
        }
        
// Step 3: Calculate width and area arrays
        vector<int> width(v.size());
        vector<int> area(v.size());
        
        for(int i = 0; i < v.size(); i++) {
            width[i] = right[i] - left[i] - 1;
            area[i] = v[i] * width[i];
        }
        
// Step 4: Find the maximum area
        int maxArea = 0;
        for(int i = 0; i < v.size(); i++) {
            if (area[i] > maxArea) {
                maxArea = area[i];
            }
        }
        
        return maxArea;
    
        }
    int maximalRectangle(vector<vector<char>>& matrix) {
        int rows=matrix.size();
        int cols=matrix[0].size();
        
    
            for(int j=0;j<cols;j++){
                v.push_back(matrix[0][j]-'0');
            }
            int mx=MAH(v);
            for(int i=1;i<rows;i++){
                for(int j=0;j<cols;j++){
                    if (matrix[i][j]=='0'){
                        v[j]=0;
                    }
                    else{
                        v[j]+= (matrix[i][j]- '0');
                    }

                }
                mx=max(mx,MAH(v));
            }
            
        return mx;
    }
};
24509