本文概述
- C ++
- Java
- Python3
- C#
例如, 考虑以下具有7个高度{6, 2, 5, 4, 4, 5, 1, 6}的条形图。可能的最大矩形是12(请参见下图, 最大面积的矩形以红色突出显示)
文章图片
我们已经讨论了基于分治法的O(nLogn)解决方案
对于这个问题。在这篇文章中, 讨论了O(n)时间解。像以前的帖子, 为简单起见, 所有条的宽度假定为1。对于每个" x"条, 我们以" x"作为矩形中最小的条计算面积。如果我们为每个小节" x"计算这样的面积并找到所有面积的最大值, 那么我们的任务就完成了。如何以" x"作为最小条形来计算面积?我们需要知道" x"左侧第一个较小(小于" x")条的索引, 以及" x"右侧第一个较小的索引。让我们将这些索引分别称为"左索引"和"右索引"。
我们从左到右遍历所有条, 并保持一堆条。每个条被推入堆栈一次。当看到较小高度的条时, 将从堆栈中弹出条。弹出条时, 我们以弹出条为最小条来计算面积。我们如何获得弹出栏的左右索引-当前索引告诉我们"右索引", 而堆栈中上一项的索引就是"左索引"。以下是完整的算法。
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[0]);
cout <
<
"Maximum area is " <
<
getMaxArea(hist, n);
return 0;
}
Java
//Java program to find maximum rectangular area in linear timeimport 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 timedef 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 stackif ( 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
时间复杂度:由于每个小节仅被推动和弹出一次, 因此此方法的时间复杂度为O(n)。
参考文献
http://www.informatik.uni-ulm.de/acm/Locals/2003/html/histogram.html
http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html
【算法题(直方图中最大的矩形区域|S2)】谢谢艾希什·阿南德(Ashish Anand)用于建议初始解决方案。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。
推荐阅读
- Mongoose insertMany()函数用法示例介绍
- 最长的子数组,任意两个不同值之间的差值恰好为K
- Linux echo命令用法示例介绍
- C中的char s[]和char *s有什么区别()
- 结构成员对齐、填充和数据打包是什么意思()
- switch和else语句有什么区别(有哪些区别?)
- SAP Labs助理开发人员(FTE)面试经验
- win7系统如何放进u盘呢?
- 大白菜u盘安装win7系统64位图文详细教程