</>Ali · LeetCode
#0084·HardStack & Queue

Largest Rectangle in Histogram

LeetCode #84 · Hard · Stack & Queue · C++ solution with worked-out approach and complexity analysis.

View on LeetCodeSource on GitHub

Approach

Monotonic Stack

Strategy

  1. 1Use a stack to store pairs of (index, height). The stack will maintain
  2. 2Iterate through the histogram:
  3. 3After iterating, process remaining bars in the stack. They extend to the
Time
O(n)
Space
O(n)
Problem description(from LeetCode)

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Examples

Example 1
Input:
heights = [2,1,5,6,2,3]
Output:
10
Note:
The largest rectangle has an area = 10 units. Input: heights = [2,4] Output: 4

Constraints

  • •1 <= heights.length <= 10^5
  • •0 <= heights[i] <= 10^4

C++ Solution

solution.cpp
class Solution {
public:
int largestRectangleArea(vector<int> &heights) {
    stack<pair<int, int>> s;
    int n = heights.size(), res = 0;
    for (int i = 0; i < n; i++) {
      int start = i;
      while (!s.empty() && heights[i] < s.top().second) {
        pair<int, int> p = s.top();
        s.pop();
        res = max(res, (i - p.first) * p.second);
        start = p.first;
      }
      s.push({start, heights[i]});
    }
    while (!s.empty()) {
      pair<int, int> p = s.top();
      s.pop();
      res = max(res, (n - p.first) * p.second);
    }

    return res;
  }
};

More Stack & Queue problems