BL
U

90. Largest Rectangle in Histogram

Med.

Problem Description

Given an array of NN non-negative integers representing the histogram's bar heights where the width of each bar is 1, find the area of the largest rectangle in the histogram.

Input Format

  • •Line 1: An integer NN (1≤N≤1051 \le N \le 10^5).
  • •Line 2: NN space-separated integers H1,…,HNH_1, \dots, H_N.

Output Format

Print the maximum rectangular area.

Example 1:
Input:
6
2 1 5 6 2 3
Output:
10
Explanation: Bars at height 5 and 6 form a rectangle of area 5 * 2 = 10.
Example 2:
Input:
2
2 4
Output:
4
Explanation: Max area is bar of height 4 (1*4=4) or both at height 2 (2*2=4).
Example 3:
Input:
1
10
Output:
10
Explanation: Single bar of height 10 has area 10.
Constraints:
  • Standard integer bounds: 32-bit signed integer or input range [1, 10^5].
  • Time complexity target: O(N) or O(N log N) where applicable.
  • Auxiliary space target: O(1) or minimal auxiliary memory.
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online