Cover image for LeetCode Hot 100 P84 Largest Rectangle in Histogram

LeetCode Hot 100 P84 Largest Rectangle in Histogram

(Updated: )
algorithm
, , ,
Timeline

timeline

2026-03-18

init

monotonic stack

Problem:

P84 Largest Rectangle in Histogram

https://leetcode.cn/problems/largest-rectangle-in-histogram/description/?envType=study-plan-v2&envId=top-100-liked

This case is a classic monotonic stack scenario. Think carefully about this problem: it’s essentially about finding the first rectangle to the left that is lower than itself, and the first rectangle to the right that is lower than itself. In fact, this is the classic ‘Next Greater’ problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <vector>
#include <stack>
using std::vector;
using std::stack;

class Solution {
    public:
        int largestRectangleArea(vector<int> &heights)
        {
                int i, n = heights.size(), max_area = 0;
                vector<int> left(n, 0);
                vector<int> right(n, n - 1);
                stack<int> stk1, stk2;

                for (i = 0; i < n; i++) {
                        while (!stk1.empty() && heights[i] < heights[stk1.top()]) {
                                right[stk1.top()] = i - 1; // right boundary
                                stk1.pop();
                        }
                        stk1.push(i);
                }

                // while (!stk.empty()) {
                //         right[stk.top()] = n - 1;
                // }

                for (i = n - 1; i >= 0; i--) {
                        while (!stk2.empty() && heights[i] < heights[stk2.top()]) {
                                left[stk2.top()] = i + 1; // left boundary
                                stk2.pop();
                        }
                        stk2.push(i);
                }

                // while (!stk.empty()) {
                //         left[stk.top()] = 0;
                // }

                for (i = 0; i < n; i++)
                        max_area = std::max(max_area, (right[i] - left[i] + 1) * heights[i]);

                return max_area;
        }
};

int main()
{
        vector<int> heights = { 2, 1, 5, 6, 2, 3 };
        Solution S;
        S.largestRectangleArea(heights);
}