[C++] Clean and Clear, With Intuitive Pictures, O(m * n * logn)
This question is very similar to \n84. Largest Rectangle in Histogram\n85. Maximal Rectangle\n\nThey are both hard questions, so don\'t be frustrated if you can
This question is very similar to \n[84. Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/)\n[85. Maximal Rectangle](https://leetcode.com/problems/maximal-rectangle/)\n\nThey are both hard questions, so don\'t be frustrated if you cannot solve it in the contest.\n\nFirst think of what we can do with a collection of histograms ? What is the largest rectangle we can form?\n![image](https://assets.leetcode.com/users/images/83adebc8-3a18-45f3-be01-f2e68d266820_1610857732.4326847.png)\n\nUnlike [84. Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/), the pillar in this question **can be rearranged !**\n![image](https://assets.leetcode.com/users/images/444fb91f-1824-4c3e-9142-788850335741_1610857694.4937603.png)\n\nFeel better now? Yes, for each pillar it can centainly form a rectangle with it\'s right neighbors.\n![image](https://assets.leetcode.com/users/images/8a7ab613-671b-4ecf-b8bc-b1159299565d_1610857939.7211492.png)\nSo we just iterate every pillar and calculate the maximum rectangle.\n\nNow comes the tricky part for this question, we can **view each row with its above as a collection of pillars!**\nAnd if the matrix[row][col] is 1 , we add the height of pillar in col by 1, ``height[row][col] = height[row - 1][col] + 1``, \nelse if matrix[row][col] is 0, we reset the height of pillar in col as 0, ``height[row][col] = 0``, because we can see it as broken pillar and hence useless.\n\n**Example**\n![image](https://assets.leetcode.com/users/images/3a302c84-c488-4320-93f9-ac2e733cc917_1610863071.022422.png)\n\n\n**Code**\n*In code I just use one dimensional array  height[col] to record heights of pillar*\n```\nclass Solution {\npublic:\n    int largestSubmatrix(vector<vector<int>>& matrix) {\n        int m = matrix.size(), n = matrix[0].size();\n        int ans = 0;\n        vector<int> height(n, 0);\n\t\t\n\t\t// view each row and its above as pillars \n        for(int i = 0; i < m; ++i){\n\t\t\t// calculate heights\n            for(int j = 0; j < n; ++j){\n                if(matrix[i][j] == 0) height[j] = 0;\n                else height[j] += 1;\n            }\n\t\t\t\n\t\t\t// sort pillars\n            vector<int> order_height = height;\n            sort(order_height.begin(), order_height.end());\n\t\t\t\n\t\t\t// iterate to get the maxium rectangle\n            for(int j = 0; j < n; ++j){\n                ans = max(ans, order_height[j] * (n - j));\n            }\n        }\n        return ans;\n    }\n};\n```
[]