【Video】Simple Solution
---\n\n# Solution Video\n\nhttps://youtu.be/A-yig8nSmT0\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget to subscribe to my channel! \u2B50\uFE0F\u2B50\uFE0F\n\n\u
---\n\n# Solution Video\n\nhttps://youtu.be/A-yig8nSmT0\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget to subscribe to my channel! \u2B50\uFE0F\u2B50\uFE0F\n\n**\u25A0 Subscribe URL**\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\nSubscribers: 4,382\nThank you for your support!\n\n---\n\n\n\n# Approach\n1. Check if the input matrix is empty, if it is return 0.\n\n2. Determine the number of columns in the matrix (n) by getting the length of the first row of the matrix.\n\n3. Create a list called heights, with n+1 elements, and initialize each element to 0.\n\n4. Create a variable called max_area and initialize it to 0.\n\n5. For each row in the matrix, do the following:\n    - Iterate through each column in the row, and update the corresponding height in the "heights" list.\n    - If the character in the matrix is "1", increment the corresponding height in the "heights" list by 1, otherwise set it to 0.\n\n6. Create an empty stack and add -1 to it.\n\n7. For each element in the "heights" list, do the following:\n    - Compare the current height to the height of the top element in the stack.\n    - If the current height is less than the height of the top element of the stack, do the following:\n        - Pop the top element of the stack and calculate the area of the rectangle formed by the popped height.\n        - Calculate the width of the rectangle by subtracting the index of the current element from the index of the new top element of the stack.\n        - Calculate the area of the rectangle by multiplying the height and width.\n        - Update the maximum area seen so far if the area of the current rectangle is larger than the current maximum.\n    - Append the index of the current element to the stack.\n\n8. Return the maximum area seen so far.\n\n# Complexity\n- Time complexity:  O(m*n)\nm is the number of rows in the input matrix and n is the number of columns. This is because we have to iterate through each element in the matrix at least once, and the time it takes to process each element is constant.\n\n- Space complexity: O(n)\nn is the number of columns in the matrix. This is because we are creating a "heights" list with n+1 elements, and a stack that could have up to n+1 elements. The rest of the variables used in the algorithm are constants and do not contribute significantly to the space complexity.\n\n# Python\n```\nclass Solution:\n    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n        if not matrix:\n            return 0\n        \n        n = len(matrix[0])\n        heights = [0] * (n + 1)\n        max_area = 0\n\n        for row in matrix:\n            for i in range(n):\n                heights[i] = heights[i] + 1 if row[i] == "1" else 0\n            \n            stack = [-1]\n            for i in range(n + 1):\n                while heights[i] < heights[stack[-1]]:\n                    h = heights[stack.pop()]\n                    w = i - stack[-1] - 1\n                    max_area = max(max_area, h * w)\n                \n                stack.append(i)\n        \n        return max_area\n```\n\n# JavaScript\n```\n/**\n * @param {character[][]} matrix\n * @return {number}\n */\nvar maximalRectangle = function(matrix) {\n    if (!matrix.length) {\n        return 0;\n    }\n    \n    const n = matrix[0].length;\n    const heights = new Array(n + 1).fill(0);\n    let maxArea = 0;\n    \n    for (let row of matrix) {\n        for (let i = 0; i < n; i++) {\n            heights[i] = row[i] === \'1\' ? heights[i] + 1 : 0;\n        }\n        \n        const stack = [-1];\n        for (let i = 0; i < n + 1; i++) {\n            while (heights[i] < heights[stack[stack.length - 1]]) {\n                const h = heights[stack.pop()];\n                const w = i - stack[stack.length - 1] - 1;\n                maxArea = Math.max(maxArea, h * w);\n            }\n            stack.push(i);\n        }\n    }\n    \n    return maxArea;    \n};\n```\n\n# Java\n```\nclass Solution {\n    public int maximalRectangle(char[][] matrix) {\n        if (matrix == null || matrix.length == 0) {\n            return 0;\n        }\n        \n        int n = matrix[0].length;\n        int[] heights = new int[n + 1];\n        int maxArea = 0;\n        \n        for (char[] row : matrix) {\n            for (int i = 0; i < n; i++) {\n                heights[i] = row[i] == \'1\' ? heights[i] + 1 : 0;\n            }\n            \n            Stack<Integer> stack = new Stack<>();\n            stack.push(-1);\n            for (int i = 0; i < n + 1; i++) {\n                while (stack.peek() != -1 && heights[i] < heights[stack.peek()]) {\n                    int h = heights[stack.pop()];\n                    int w = i - stack.peek() - 1;\n                    maxArea = Math.max(maxArea, h * w);\n                }\n                stack.push(i);\n            }\n        }\n        \n        return maxArea;        \n    }\n}\n```\n\n# C++\n```\nclass Solution {\npublic:\n    int maximalRectangle(vector<vector<char>>& matrix) {\n        if (matrix.empty()) {\n            return 0;\n        }\n        \n        int n = matrix[0].size();\n        vector<int> heights(n + 1);\n        int maxArea = 0;\n        \n        for (auto row : matrix) {\n            for (int i = 0; i < n; i++) {\n                heights[i] = row[i] == \'1\' ? heights[i] + 1 : 0;\n            }\n            \n            stack<int> st;\n            st.push(-1);\n            for (int i = 0; i < n + 1; i++) {\n                while (st.top() != -1 && heights[i] < heights[st.top()]) {\n                    int h = heights[st.top()];\n                    st.pop();\n                    int w = i - st.top() - 1;\n                    maxArea = max(maxArea, h * w);\n                }\n                st.push(i);\n            }\n        }\n        \n        return maxArea;        \n    }\n};\n```
['C++', 'Java', 'Python3', 'JavaScript']