This is one of those problems where the clean idea matters more than the amount of code. For 84. Largest Rectangle in Histogram, the solution in this repository is mainly a dynamic programming solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. 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:
- https://www.cnblogs.com/grandyang/p/4322653.html
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are largestRectangleArea, tmp, leftLower, rightLower.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- The stack stores unfinished context, which is usually the cleanest way to handle nested or monotonic structure.
- 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:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
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//https://www.cnblogs.com/grandyang/p/4322653.html
02//Runtime: 32 ms, faster than 15.56% of C++ online submissions for Largest Rectangle in Histogram.
03//Memory Usage: 13.9 MB, less than 5.72% of C++ online submissions for Largest Rectangle in Histogram.
04class Solution {
05public:
06 int largestRectangleArea(vector<int>& heights) {
07 int n = heights.size();
08 int ans = 0;
09
10 for(int i = 0; i < n; i++){
11 if(i+1 < n && heights[i] <= heights[i+1]){
12 continue;
13 }
14 /*
15 when the next element < current element or
16 this is the last element
17
18 because when next element >= current element,
19 then current element can be considered when calculating area
20
21 so for efficiency purpose,
22 we start to calculate candidate ans if
23 the next element is smaller than current element
24 */
25 int minH = INT_MAX;
26 for(int j = i; j >= 0; j--){
27 minH = min(minH, heights[j]);
28 ans = max(ans, minH * (i-j+1));
29 }
30 }
31
32 return ans;
33 }
34};
35
36//monotonic stack
37//https://www.cnblogs.com/grandyang/p/4322653.html
38//Runtime: 24 ms, faster than 40.27% of C++ online submissions for Largest Rectangle in Histogram.
39//Memory Usage: 14.1 MB, less than 5.72% of C++ online submissions for Largest Rectangle in Histogram.
40class Solution {
41public:
42 int largestRectangleArea(vector<int>& heights) {
43 //increasing stack, start to calculate area when we meet smaller element
44 stack<int> stk;
45 int ans = 0;
46 //to ensure the last element will be used to calculate area
47 heights.push_back(0);
48
49 for(int i = 0; i < heights.size(); i++){
50 //start to calculate area when we find a smaller element
51 //continue the process until i's height >= stk.top()'s
52 while(!stk.empty() && heights[i] < heights[stk.top()]){
53 int cur = stk.top(); stk.pop();
54 /*
55 i-1: the right boundary of rectangle
56 we meet i, which is lower than stk.top(),
57 it is only used to trigger calculating area,
58 and our rectangle does not include column i
59
60 stk.top()+1: the left boundary of rectangle
61 NOTE: cur and stk.top() are different!!
62 stk.top() if the index of rectangle which is even lower than cur
63 our rectangle can only extend to stk.top()+1
64 because stk.top()'s height is lower than heights[cur]
65
66 heights[cur]: lowest element's height
67 */
68 // cout << heights[cur] << " * " << (stk.empty() ? i : (i -1 - stk.top())) << ", " << stk.size() << " elements in stack." << endl;
69 // if(!stk.empty()){
70 // vector<int> tmp(&stk.top()+1-stk.size(), &stk.top() + 1);
71 // cout << "stack elements: ";
72 // for(int e : tmp){
73 // cout << e << " ";
74 // }
75 // cout << endl;
76 // }
77 ans = max(ans, heights[cur] * (stk.empty() ? i : (i- 1 - stk.top())));
78 }
79 //when stk.empty() || heights[i] >= heights[stk.top()]
80 stk.push(i);
81 }
82
83 return ans;
84 }
85};
86
87//DP
88//https://leetcode.com/problems/largest-rectangle-in-histogram/discuss/28902/5ms-O(n)-Java-solution-explained-(beats-96)
89//Runtime: 24 ms, faster than 40.27% of C++ online submissions for Largest Rectangle in Histogram.
90//Memory Usage: 14.2 MB, less than 5.72% of C++ online submissions for Largest Rectangle in Histogram.
91class Solution {
92public:
93 int largestRectangleArea(vector<int>& heights) {
94 int n = heights.size();
95
96 vector<int> leftLower(n);
97 vector<int> rightLower(n);
98 int ans = 0;
99
100 for(int i = 0; i < n; i++){
101 int p = i-1;
102 /*
103 if i-1's height >= i's height,
104 we need to go backward.
105 since heights[p] >= heights[i] and
106 all q in [leftLower[p]+1, p-1] >= heights[p],
107 so we skip these q and choose leftLower[p] as our next trial
108 */
109 while(p >= 0 && heights[p] >= heights[i]){
110 p = leftLower[p];
111 }
112 leftLower[i] = p;
113 }
114
115 for(int i = n-1; i >= 0; i--){
116 int p = i+1;
117
118 while(p < n && heights[p] >= heights[i]){
119 p = rightLower[p];
120 }
121 rightLower[i] = p;
122 }
123
124 for(int i = 0; i < n; i++){
125 ans = max(ans, (rightLower[i]-leftLower[i]-1) * heights[i]);
126 }
127
128 return ans;
129 }
130};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.