# 算法题：直方图中最大的矩形区域|S2

2021年4月19日12:20:38 发表评论 561 次浏览

## 本文概述

1)创建一个空堆栈。

2)从第一个小节开始, 然后对每个小节" hist [i]"执行跟踪, 其中" i"的范围从0到n-1。

……a)如果堆栈为空或hist [i]高于堆栈顶部的条, 则按" i"进行堆栈。

……b)如果此栏小于堆栈顶部, 则在堆栈顶部较大的同时, 继续移除堆栈顶部。令删除的条为hist [tp]。用hist [tp]作为最小条形来计算矩形的面积。对于hist [tp], "左索引"是堆栈中的上一个项目(在tp之前), "右索引"是" i"(当前索引)。

3)如果堆栈不是空的, 则一个接一个地从堆栈中删除所有条, 并对每个已删除的条执行步骤2.b。

## C ++

``````//C++ program to find maximum rectangular area in
//linear time
#include<bits/stdc++.h>
using namespace std;

//The main function to find the maximum rectangular
//area under given histogram with n bars
int getMaxArea( int hist[], int n)
{
//Create an empty stack. The stack holds indexes
//of hist[] array. The bars stored in stack are
//always in increasing order of their heights.
stack<int> s;

int max_area = 0; //Initialize max area
int tp;  //To store top of stack
int area_with_top; //To store area with top bar
//as the smallest bar

//Run through all bars of given histogram
int i = 0;
while (i <n)
{
//If this bar is higher than the bar on top
//stack, push it to stack
if (s.empty() || hist[s.top()] <= hist[i])
s.push(i++);

//If this bar is lower than top of stack, //then calculate area of rectangle with stack
//top as the smallest (or minimum height) bar.
//'i' is 'right index' for the top and element
//before top in stack is 'left index'
else
{
tp = s.top();  //store the top index
s.pop();  //pop the top

//Calculate the area with hist[tp] stack
//as smallest bar
area_with_top = hist[tp] * (s.empty() ? i :
i - s.top() - 1);

//update max area, if needed
if (max_area <area_with_top)
max_area = area_with_top;
}
}

//Now pop the remaining bars from stack and calculate
//area with every popped bar as the smallest bar
while (s.empty() == false )
{
tp = s.top();
s.pop();
area_with_top = hist[tp] * (s.empty() ? i :
i - s.top() - 1);

if (max_area <area_with_top)
max_area = area_with_top;
}

return max_area;
}

//Driver program to test above function
int main()
{
int hist[] = {6, 2, 5, 4, 5, 1, 6};
int n = sizeof (hist)/sizeof (hist);
cout <<"Maximum area is " <<getMaxArea(hist, n);
return 0;
}``````

## Java

``````//Java program to find maximum rectangular area in linear time

import java.util.Stack;

public class RectArea
{
//The main function to find the maximum rectangular area under given
//histogram with n bars
static int getMaxArea( int hist[], int n)
{
//Create an empty stack. The stack holds indexes of hist[] array
//The bars stored in stack are always in increasing order of their
//heights.
Stack<Integer> s = new Stack<>();

int max_area = 0 ; //Initialize max area
int tp;  //To store top of stack
int area_with_top; //To store area with top bar as the smallest bar

//Run through all bars of given histogram
int i = 0 ;
while (i <n)
{
//If this bar is higher than the bar on top stack, push it to stack
if (s.empty() || hist[s.peek()] <= hist[i])
s.push(i++);

//If this bar is lower than top of stack, then calculate area of rectangle
//with stack top as the smallest (or minimum height) bar. 'i' is
//'right index' for the top and element before top in stack is 'left index'
else
{
tp = s.peek();  //store the top index
s.pop();  //pop the top

//Calculate the area with hist[tp] stack as smallest bar
area_with_top = hist[tp] * (s.empty() ? i : i - s.peek() - 1 );

//update max area, if needed
if (max_area <area_with_top)
max_area = area_with_top;
}
}

//Now pop the remaining bars from stack and calculate area with every
//popped bar as the smallest bar
while (s.empty() == false )
{
tp = s.peek();
s.pop();
area_with_top = hist[tp] * (s.empty() ? i : i - s.peek() - 1 );

if (max_area <area_with_top)
max_area = area_with_top;
}

return max_area;

}

//Driver program to test above function
public static void main(String[] args)
{
int hist[] = { 6 , 2 , 5 , 4 , 5 , 1 , 6 };
System.out.println( "Maximum area is " + getMaxArea(hist, hist.length));
}
}
//This code is Contributed by Sumit Ghosh``````

## Python3

``````# Python3 program to find maximum
# rectangular area in linear time

def max_area_histogram(histogram):

# This function calulates maximum
# rectangular area under given
# histogram with n bars

# Create an empty stack. The stack
# holds indexes of histogram[] list.
# The bars stored in the stack are
# always in increasing order of
# their heights.
stack = list ()

max_area = 0 # Initialize max area

# Run through all bars of
# given histogram
index = 0
while index <len (histogram):

# If this bar is higher
# than the bar on top
# stack, push it to stack

if ( not stack) or (histogram[stack[ - 1 ]] <= histogram[index]):
stack.append(index)
index + = 1

# If this bar is lower than top of stack, # then calculate area of rectangle with
# stack top as the smallest (or minimum
# height) bar.'i' is 'right index' for
# the top and element before top in stack
# is 'left index'
else :
# pop the top
top_of_stack = stack.pop()

# Calculate the area with
# histogram[top_of_stack] stack
# as smallest bar
area = (histogram[top_of_stack] *
((index - stack[ - 1 ] - 1 )
if stack else index))

# update max area, if needed
max_area = max (max_area, area)

# Now pop the remaining bars from
# stack and calculate area with
# every popped bar as the smallest bar
while stack:

# pop the top
top_of_stack = stack.pop()

# Calculate the area with
# histogram[top_of_stack]
# stack as smallest bar
area = (histogram[top_of_stack] *
((index - stack[ - 1 ] - 1 )
if stack else index))

# update max area, if needed
max_area = max (max_area, area)

# Return maximum area under
# the given histogram
return max_area

# Driver Code
hist = [ 6 , 2 , 5 , 4 , 5 , 1 , 6 ]
print ( "Maximum area is" , max_area_histogram(hist))

# This code is contributed
# by Jinay Shah``````

## C#

``````//C# program to find maximum
//rectangular area in linear time
using System;
using System.Collections.Generic;

class GFG
{
//The main function to find the
//maximum rectangular area under
//given histogram with n bars
public static int getMaxArea( int [] hist, int n)
{
//Create an empty stack. The stack
//holds indexes of hist[] array
//The bars stored in stack are always
//in increasing order of their heights.
Stack<int> s = new Stack<int>();

int max_area = 0; //Initialize max area
int tp; //To store top of stack
int area_with_top; //To store area with top
//bar as the smallest bar

//Run through all bars of
//given histogram
int i = 0;
while (i <n)
{
//If this bar is higher than the
//bar on top stack, push it to stack
if (s.Count == 0 || hist[s.Peek()] <= hist[i])
{
s.Push(i++);
}

//If this bar is lower than top of stack, //then calculate area of rectangle with
//stack top as the smallest (or minimum
//height) bar. 'i' is 'right index' for
//the top and element before top in stack
//is 'left index'
else
{
tp = s.Peek(); //store the top index
s.Pop(); //pop the top

//Calculate the area with hist[tp]
//stack as smallest bar
area_with_top = hist[tp] *
(s.Count == 0 ? i : i - s.Peek() - 1);

//update max area, if needed
if (max_area <area_with_top)
{
max_area = area_with_top;
}
}
}

//Now pop the remaining bars from
//stack and calculate area with every
//popped bar as the smallest bar
while (s.Count> 0)
{
tp = s.Peek();
s.Pop();
area_with_top = hist[tp] *
(s.Count == 0 ? i : i - s.Peek() - 1);

if (max_area <area_with_top)
{
max_area = area_with_top;
}
}

return max_area;

}

//Driver Code
public static void Main( string [] args)
{
int [] hist = new int [] {6, 2, 5, 4, 5, 1, 6};
Console.WriteLine( "Maximum area is " +
getMaxArea(hist, hist.Length));
}
}

//This code is contributed by Shrikant13``````

``Maximum area is 12``

http://www.informatik.uni-ulm.de/acm/Locals/2003/html/histogram.html

http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html 