[JavaScript] 85. Maximal Rectangle
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n- 1-dimensional: https://leetcode.com/problems/largest-rectangle-in-histo
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n- 1-dimensional: https://leetcode.com/problems/largest-rectangle-in-histogram/\n\nSolution: https://leetcode.com/problems/largest-rectangle-in-histogram/solutions/3297538/javascript-84-largest-rectangle-in-histogram/\n\n- 2-dimensional: https://leetcode.com/problems/maximal-rectangle/\n\nSolution: below\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n\nGood one\n\n1\n```\nvar maximalRectangle = function (aa) {\n    let m = aa.length,\n        n = aa[0].length;\n\n    let widthOnLeftTillHere = Array.from({ length: m }, () =>\n        new Array(n).fill(0)\n    );\n    for (let r = 0; r < m; r++)\n        for (let c = 0; c < n; c++)\n            if (aa[r][c] === "1") {\n                widthOnLeftTillHere[r][c] =\n                    (widthOnLeftTillHere[r][c - 1] || 0) + 1;\n            }\n\n    let maxArea = 0;\n    for (let r = 0; r < m; r++)\n        for (let c = 0; c < n; c++)\n            if (aa[r][c] === "1") {\n                let minWidthGoingUp = Infinity;\n                let increasingHeight = 1;\n                for (let r2 = r; r2 >= 0; r2--, increasingHeight++) {\n                    minWidthGoingUp = Math.min(\n                        minWidthGoingUp,\n                        widthOnLeftTillHere[r2][c]\n                    );\n                    maxArea = Math.max(\n                        maxArea,\n                        minWidthGoingUp * increasingHeight\n                    );\n                }\n            }\n    return maxArea;\n};\n```\n\n2 - Optimized, a bit difficult to understand at begin\n```\nfunction maximalRectangle(aa) {\n    let m = aa.length,\n        n = aa[0].length;\n\n    let heights = new Array(n + 1).fill(0), // this row heights, last col is 0\n        maxArea = 0;\n\n    for (let r = 0; r < m; r++) {\n        let cols = []; // prev increasing columns - stack\n        cols.top = () => cols[cols.length - 1]; // get column left on top of stack\n\n        for (let c = 0; c <= n; c++) {\n            if (c < n) {\n                if (aa[r][c] === "1") heights[c]++;\n                else heights[c] = 0;\n            }\n\n            while (cols.length && heights[cols.top()] > heights[c]) {\n                let height = heights[cols.pop()]; // prev column height\n                let width = cols.length ? c - cols.top() - 1 : c; // prev prev column to cur column width\n                maxArea = Math.max(maxArea, width * height);\n            }\n            cols.push(c);\n        }\n    }\n    return maxArea;\n}\n```\n
['JavaScript']