Let's make this one less mysterious. For 85. Maximal Rectangle, the solution in this repository is mainly a dynamic programming solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: dynamic programming, two pointers, stack, sliding window.
The notes already sitting in the source point us in the right direction:
- monotonic stack, 84. Largest Rectangle in Histogram
- https://www.cnblogs.com/grandyang/p/4322667.html
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are maximalRectangle, heights, height, left, right.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- The stack stores unfinished context, which is usually the cleanest way to handle nested or monotonic structure.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//monotonic stack, 84. Largest Rectangle in Histogram
02//https://www.cnblogs.com/grandyang/p/4322667.html
03//Runtime: 92 ms, faster than 20.43% of C++ online submissions for Maximal Rectangle.
04//Memory Usage: 12 MB, less than 35.98% of C++ online submissions for Maximal Rectangle.
05class Solution {
06public:
07 int maximalRectangle(vector<vector<char>>& matrix) {
08 int m = matrix.size();
09 if(m == 0) return 0;
10 int n = matrix[0].size();
11 if(n == 0) return 0;
12
13 //push back 0 to "h"!
14 vector<int> heights(n+1);
15 int ans = 0;
16
17 for(int i = 0; i < m; i++){
18 /*
19 we view each row as a problem of 84.Largest Rectangle in Histogram
20 */
21 stack<int> stk;
22 /*
23 here the heights.size() is the size of h
24 after pushing a 0 into it,
25 so it's n+1,
26 that's because we want the last element of
27 original h to be processed
28 */
29 for(int j = 0; j < heights.size(); j++){
30 //update heights for current row
31 if(j < n){
32 heights[j] = (matrix[i][j] == '1') ? heights[j]+1 : 0;
33 }
34 //same as 84. Largest Rectangle in Histogram
35 while(!stk.empty() && heights[j] < heights[stk.top()]){
36 int cur = stk.top(); stk.pop();
37 ans = max(ans, heights[cur] * (stk.empty() ? j : (j-1-stk.top())));
38 }
39 stk.push(j);
40 }
41 }
42
43 return ans;
44 }
45};
46
47//DP
48//https://www.cnblogs.com/grandyang/p/4322667.html
49//https://leetcode.com/problems/maximal-rectangle/discuss/29054/Share-my-DP-solution/175299
50//Runtime: 52 ms, faster than 40.28% of C++ online submissions for Maximal Rectangle.
51//Memory Usage: 11 MB, less than 61.11% of C++ online submissions for Maximal Rectangle.
52class Solution {
53public:
54 int maximalRectangle(vector<vector<char>>& matrix) {
55 int m = matrix.size();
56 if(m == 0) return 0;
57 int n = matrix[0].size();
58 if(n == 0) return 0;
59
60 //current number of continuous '1' at column i
61 vector<int> height(n, 0);
62 /*
63 left boundary of continuous '1' in current row
64 leftmost p which all q in [p, i-1] all satisfies height[q] >= height[i]
65
66 because initial values of height is 0 for all i,
67 so all q in [0,i-1] has height[q] = 0 >= height[i] = 0,
68 so the initial value of the left array is all 0
69 */
70 vector<int> left(n, 0);
71 /*
72 right boundary of continuous '1' in current row
73 rightmost p which all q in [i+1, q] all satisfies height[q] >= height[i]
74
75 because initial values of height is 0 for all i,
76 so all q in [i+1,n-1] has height[q] = 0 >= height[i] = 0,
77 so the initial value of the right array is all n-1
78 */
79 vector<int> right(n, n-1);
80 int ans = 0;
81
82 for(int i = 0; i < m; i++){
83 //left boundary for current row
84 int cur_left = 0;
85 //right boundary for current row
86 int cur_right = n-1;
87 for(int j = 0; j < n; j++){
88 if(matrix[i][j] == '1'){
89 height[j]++;
90 /*
91 within the boundary of previous of height array and
92 within the boundary of current row
93 */
94 left[j] = max(left[j], cur_left);
95 //cur_left maintains the same when we meet continuous '1'
96 }else{
97 height[j] = 0;
98 /*
99 since height[j] = 0, by definition, all q in [0, j-1]
100 satisfies height[q] >= height[j], so left[j] should be set to 0
101
102 set to 0 so that it won't affect
103 the result of "left[j] = max(left[j], cur_left);"
104 */
105 left[j] = 0;
106 /*
107 will be used when we meet next '1'
108
109 leftmost boundary of continuous '1' should be at least j+1
110 */
111 cur_left = j+1;
112 }
113 }
114
115 for(int j = n-1; j >= 0; j--){
116 if(matrix[i][j] == '1'){
117 right[j] = min(right[j], cur_right);
118 // cout << "(" << i << ", " << j << "): [" << left[j] << ", " << right[j] << "] x " << height[j] << endl;
119 ans = max(ans, (right[j]-left[j]+1) * height[j]);
120 }else{
121 /*
122 set to n-1 so that it won't affect
123 the result of "right[j] = min(right[j], cur_right);"
124 */
125 right[j] = n-1;
126 cur_right = j-1;
127 }
128 }
129 }
130
131 return ans;
132 }
133};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.