Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Stack & Queue

Largest Rectangle in Histogram

Hard · Stack & Queue · Asked at Google, Amazon, Microsoft, Adobe

Bars of width 1 have the given heights. Print the area of the largest rectangle inside the histogram.

Input

First line: n. Second line: n heights.

Output

The largest area.

Constraints

For each bar find the nearest smaller bar on both sides with a monotonic stack.

Example 1

Input

6
2 1 5 6 2 3

Output

10

Example 2

Input

2
2 4

Output

4

Hints

  1. In the best rectangle, some bar is the shortest one — and the rectangle stretches left and right until a shorter bar blocks it.
  2. Use a stack of increasing heights. When a shorter bar arrives, pop: the popped bar's rectangle spans from the new stack top + 1 to i − 1.

Approach

Keep a stack of indices with increasing heights. When h[i] is lower than the top, pop the top index t: bar t can't extend to i, and the bar now on top is the nearest shorter bar on its left. So its rectangle has height h[t] and width i − (newTop + 1), or i if the stack is empty. Adding a final bar of height 0 flushes the stack. Each index is pushed and popped once. Areas reach 10^9, so use 64 bits.

Complexity: O(n) time · O(n) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> h(n);
    for (auto &x : h) cin >> x;
    h.push_back(0);  // sentinel flushes the stack at the end
    vector<int> st;
    long long best = 0;
    for (int i = 0; i <= n; i++) {
        while (!st.empty() && h[st.back()] > h[i]) {
            long long height = h[st.back()];
            st.pop_back();
            long long width = st.empty() ? i : i - st.back() - 1;
            best = max(best, height * width);
        }
        st.push_back(i);
    }
    cout << best << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n = data[0]
h = data[1 : n + 1] + [0]  # sentinel flushes the stack at the end
stack, best = [], 0
for i, x in enumerate(h):
    while stack and h[stack[-1]] > x:
        height = h[stack.pop()]
        width = i - stack[-1] - 1 if stack else i
        best = max(best, height * width)
    stack.append(i)
print(best)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] h = new long[n + 1];  // h[n] = 0 is a sentinel
        for (int i = 0; i < n; i++) h[i] = sc.nextLong();
        int[] st = new int[n + 1];
        int top = 0;
        long best = 0;
        for (int i = 0; i <= n; i++) {
            while (top > 0 && h[st[top - 1]] > h[i]) {
                long height = h[st[--top]];
                long width = top == 0 ? i : i - st[top - 1] - 1;
                best = Math.max(best, height * width);
            }
            st[top++] = i;
        }
        System.out.println(best);
    }
}

Solve Largest Rectangle in Histogram online · All practice problems