Monotonic stack|DP+count successive '1's||16ms Beats 99.62%
Intuition\n Describe your first thoughts on how to solve this problem. \nSimilar to solving 84. Largest Rectangle in Histogram.\n\n2nd approach uses the old DP 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSimilar to solving 84. Largest Rectangle in Histogram.\n\n2nd approach uses the old DP solution for LC 84.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nIn this question, one has to build the histogram (`h` in code) for each row.\nThe part for monotonic stack is almost the same like in solving Leetcode 84. Largest Rectangle in Histogram\n\nThe pattern for monotonic stack is used for many Leetcode\'s hard questions for which the variant is applied to LC 84 & LC 85 as follows\n```\nst={-1}; //let stack contain an element -1\ntop=0;\nfor (r=0; r<=col; r++){//Moving right index\n    // Count the successive \'1\'s & store in h[j]\n    h[j]=compute_for_h(j);\n\n    // monotonic stack has at least element -1\n    while(st has more than -1 and (j==col or h[j]<h[st[top]])){\n        m=st[top--];//pop\n        l=st[top];//left index\n        w=r-l-1;\n        area=h[m]*w;\n        maxArea=max(maxArea, area);\n    }\n    st[++top]=j;//push\n}\n```\n\nThe following is generated by random data to show the maxArea for the histogram `h`. The green area is in fact the cells with \'1\' which are connected to the cells \'1\' in the row for considering.\n![hist_maxArea.png](https://assets.leetcode.com/users/images/2bd2c140-882b-4394-b43b-325ff1b7f92a_1712987673.8139648.png)\n[Please turn on english subtitles. Solving [42. Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/solutions/5010020/monotonic-stack-vs-priority-queueusing-pyplot-explain3ms-beats-9910/) use a similar way of monotonic stack, in the film is shown how to use pyplot.bar to visualize the data, especially for the area computing.]\n[https://youtu.be/IERpc-YJIT0?si=HaXCPOHz83goH3yf](https://youtu.be/IERpc-YJIT0?si=HaXCPOHz83goH3yf)\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(row\\times col)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(col)$$\n# Code||C++ 16ms Beats 99.62%\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    int maximalRectangle(vector<vector<char>>& matrix) {\n        const unsigned short row=matrix.size(), col=matrix[0].size();\n        if (row==1 && col==1) return matrix[0][0]==\'1\';\n        vector<unsigned short> h(col+1);//height \n        int maxArea=0;\n\n        for(int i=0; i<row; i++){\n            vector<int> st={-1}; //stack will not be empty\n            for (int j=0; j<=col; j++){\n                // Count the successive \'1\'s & store in h[j]\n                h[j]=(j==col||matrix[i][j]==\'0\')?0:h[j]+1;\n\n                // monotonic stack has at least element -1\n                while(st.size()>1 && (j==col||h[j]<h[st.back()])){\n                    const int m=st.back();\n                    st.pop_back();\n                    const int w=j-st.back()-1;\n                    const int area=h[m]*w;\n                    maxArea=max(maxArea, area);\n                }\n                st.push_back(j);\n            }\n        }\n        return maxArea;\n    }\n};\n\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```\n# Python Code\n```\nclass Solution:\n    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n        r, c=len(matrix), len(matrix[0])\n        if r==1 and c==1:\n            if matrix[0][0]==\'1\': return 1\n            else: return 0\n        h=[0]*(c+1)\n        maxArea=0\n\n        for i, row  in enumerate(matrix):\n            st=[-1] \n            row.append(\'0\')\n            for j, x in enumerate(row):\n                # build h\n                if x==\'1\': h[j]+=1\n                else: h[j]=0\n                # mononotonic stack has at leat element -1\n                while len(st)>1 and (j==c or h[j]<h[st[-1]]):\n                    m=st[-1]\n                    st.pop()\n                    w=j-st[-1]-1\n                    area=h[m]*w\n                    maxArea=max(maxArea, area)\n                st.append(j)\n        return maxArea\n\n        \n```\n# C++ using DP solution for LC 84||19ms beats 99.01%\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    //l: the x-coordinate of the bar to the left with height h[l] < h[i].\n    //r: the x-coordinate of the bar to the right with height h[r] < h[i].\n    int largestRectangleArea(vector<int>& heights, int n) {\n        //adopt from leetcode 84 which is a 2-pass solution using DP\n        if (n==0) return 0;\n        vector<int> l(n),  r(n);\n        r[n-1]=n, l[0]=-1;\n\n        for(int i=1; i<n; i++){\n            int p=i-1;\n            while(p>=0 && heights[p]>=heights[i])\n                p=l[p];\n            l[i]=p;\n        }\n\n        int maxA=heights[n-1]*(r[n-1]-l[n-1]-1);\n        for(int i=n-2; i>=0; i--){\n            int p=i+1;\n            while(p<n && heights[p]>=heights[i])\n                p=r[p];\n            r[i]=p;\n            maxA=max(maxA, heights[i]*(r[i]-l[i]-1));\n        }\n    //    cout<<maxA<<endl;\n        return maxA;\n    }\n\n    int maximalRectangle(vector<vector<char>>& matrix) {\n        const unsigned short row=matrix.size(), col=matrix[0].size();\n        if (row==1 && col==1) return matrix[0][0]==\'1\';\n        vector<int> h(col);//height \n        int maxArea=0;\n\n        for(int i=0; i<row; i++){\n            for (int j=0; j<col; j++){\n                // Count the successive \'1\'s & store in h[j]\n                h[j]=(matrix[i][j]==\'0\')?0:h[j]+1;\n            }\n            maxArea=max(maxArea, largestRectangleArea(h, col));\n        }\n        return maxArea;\n    }\n};\n\n```
['Dynamic Programming', 'Monotonic Stack', 'C++', 'Python3']