Largest Rectangle in Histogram

Largest Rectangle in Histogram

Hard PHP PHP Arrays 28 views
Explanation Complexity

Problem Statement

Given bar heights, find the largest rectangle area in the histogram.

Input Format

First n. Next line n heights.

Output Format

One integer area.

Example

7
2 1 5 6 2 3
10

Constraints

n

Input / Output Format

Input Format
First n. Next line n heights.
Output Format
One integer area.
Constraints
n

Examples

Input:
7 2 1 5 6 2 3
Output:
10

Example Solution (Public)

PHP 
<?php
$inputText=trim(stream_get_contents(STDIN));
if($inputText==='') exit;
$tokens=preg_split('/\\s+/', $inputText);
$i=0; $n=intval($tokens[$i++] ?? 0);
$h=[];
for($k=0;$k<$n;$k++) $h[] = intval($tokens[$i++] ?? 0);
$st=[];
$best=0;
for($i=0;$i<=$n;$i++){
  $cur=($i===$n)?0:$h[$i];
  $start=$i;
  while($st && $st[count($st)-1][1] > $cur){
    [$pos,$height]=array_pop($st);
    $best=max($best,$height*($i-$pos));
    $start=$pos;
  }
  $st[] = [$start,$cur];
}
echo $best;
?>

Official Solution Code

<?php
$inputText=trim(stream_get_contents(STDIN));
if($inputText==='') exit;
$tokens=preg_split('/\\s+/', $inputText);
$i=0; $n=intval($tokens[$i++] ?? 0);
$h=[];
for($k=0;$k<$n;$k++) $h[] = intval($tokens[$i++] ?? 0);
$st=[];
$best=0;
for($i=0;$i<=$n;$i++){
  $cur=($i===$n)?0:$h[$i];
  $start=$i;
  while($st && $st[count($st)-1][1] > $cur){
    [$pos,$height]=array_pop($st);
    $best=max($best,$height*($i-$pos));
    $start=$pos;
  }
  $st[] = [$start,$cur];
}
echo $best;
?>
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.