Java 中直方图的最大矩形面积

2025年3月17日 | 阅读11分钟

在本节中，我们将探讨如何在直方图中计算最大矩形面积。

直方图中的最大矩形面积是什么？

要创建的最大矩形应由连续的条形组成。为了简单起见，我们将假定每个条形的宽度为 1。

例如，对于具有 7 个条形高度为 {7, 3, 6, 5, 6, 2, 7} 的直方图，可能的最大矩形面积为 15。最大面积以黄色突出显示。

Maximum Rectangular Area in a Histogram in Java

让我们讨论解决此问题的各种方法。

朴素方法

在此方法中，我们将逐一考虑每个条形作为起点，并从该起点开始，每次通过逐一考虑下一个条形来计算矩形面积。每次计算矩形面积时，我们将其与当前最大面积进行比较（最初，最大面积初始化为 0）。

文件名：LargestRectArea.java

public class LargestRectArea 
{

// a method that finds the 
// minimum between a & b
int findMin(int a, int b)
{
  int min = (a > b) ? b : a; 
  return min;
}

// a method that finds the 
// maximum between a & b
int findMax(int a, int b)
{
  int max = (a > b) ? a : b; 
  return max;
}

// the main method
public static void main(String argvs[])
{
// creating an object of the class LargestRectArea
LargestRectArea obj = new LargestRectArea();

// input array in which each element represents the
// height of the bar of the histogram
int arr[] = {7, 3, 6, 5, 6, 2, 7};
int size = arr.length;

int maxArea = 0;

for(int i = 0; i < size; i++)
{
// arr[i] is the first bar of the 
// maximum rectangular area
int temp = arr[i];
maxArea = obj.findMax(temp, maxArea);
for(int j = i + 1; j < size; j++)
{
    temp = obj.findMin(temp, arr[j]);
    maxArea = obj.findMax(maxArea, temp * (j - i + 1));
}
}
System.out.println("The maximum rectangular area is: " + maxArea);
}
}

输出

The maximum rectangular area is: 15

时间复杂度：在上面的程序中，我们使用了 2 次幂的嵌套 for 循环。因此，该程序的总复杂度为 O(n²)，其中 n 是输入数组中存在的元素总数。

分治法

该概念是找到输入数组中值为最小的索引。一旦找到值为最小的索引，最大面积就是以下三个值中的最大值。

最小值的左侧的最大面积（不包括最小值）
最小值的右侧的最大面积（不包括最小值）。
条形总数乘以最小条形值。

观察下面的程序。

import java.util.*;

public class LargestRectArea1
{
static int hist[];
static int segTree[];

// A utility method to find the minimum of the three integers
public int max(int a, int b, int c)
{ return Math.max(Math.max(a, b), c); }

// A utility method to get the minimum of the two numbers in the hist[]
public int findMin(int a, int b)
{
if (a == -1)
{ return b; }
if (b == -1) { return a; }
return (hist[a] < hist[b]) ? a : b;
}

// A utility method to retrieve the middle idx using the corner indices.
public int findMid(int s, int e)
{ return s + (e - s) / 2; }

// A recursive method for getting the index of the minimum value in the provided range of
// the indices. The following are the different parameters for this method.

// hist - The input array for which the segment tree is made
// segTree - segment tree pointer
// idx -. It represents the curr node index in the seg tree. Initially zero is passed as the 
// root is always at the index zero
// si & ei - si = starting index and ei = ending index of the segment as shown by the curr // node, i.e., si[idx]
// qs & qe - Query Start = qs & Query End = qe 
public int findIndexUtility( int si, int ei, int qs, int qe, int idx)
{
// If the segment of this node is in the portion of the provided range, then send the
// minimum value of segment
if (qs <= si && qe >= ei)
{
return segTree[idx];
}

// If the segment of this node is outside the given range
if (ei < qs || si > qe)
{
return -1;
}

// If the part of this segment is overlapping with the provided range
int mid = findMid(si, ei);
return findMin( findIndexUtility(si, mid, qs, qe, 2 * idx + 1),
	findIndexUtility( mid + 1, ei, qs, qe, 2 * idx + 2));
}

// the method returns the index of the minimum element in the range from the index qs (query begin) to
// query end (qe). It uses the findIndexUtil() method
public int returnIndex( int s, int qb, int qe)
{
// Check for the out of range input values
if (qb < 0 || qe > s - 1 || qb > qe)
{
System.out.print("The given input is not valid");
return -1;
}

return findIndexUtility( 0, s - 1, qb, qe, 0);
}

// A recursive method that makes the Segment Tree for the hist[s ... e].
// si is the index of the current node in the segment tree segTree
public int constructSTUtililty(int s, int e, int si)
{
// When there is only one element in the tree, keep it in the curr node of
// the segment tree and then return
if (s == e)
{
return (segTree[si] = s);
}

// When more than one element is present, we have to do the recursion for the right and
// the left subtrees and store the minimum of the two values into this node
int mid = findMid(s, e);
segTree[si] = findMin(constructSTUtililty(s, mid, si * 2 + 1),
		constructSTUtililty(mid + 1, e, si * 2 + 2));
return segTree[si];
}

// method for making the seg tree from the given array. The method
// that assigns the memory for the segment tree and invokes the constructSTUtililty() 
// method for
// filling the memory that is allocated
public void constructSegTree(int s)
{
// Allocating memory for the segment tree
int x = (int)(Math.ceil(Math.log(s))); // Height of the segment tree
int maxSize = 2 * (int)Math.pow(2, x) - 1; // The Maximum size of the segment tree
segTree = new int[maxSize * 2];

constructSTUtililty( 0, s - 1, 0);

}

// A method that recursively looks for the rectangular area that is maximum.
// It uses the segment tree 'segTree' to look for the minimum value in hist[l ... r]
public int findMaxAreaRec( int s, int lt, int rt)
{
// handling the Base cases
if (lt > rt)  return Integer.MIN_VALUE;
if (lt == rt)  return hist[lt];

// Find index of the minimum value in given range
// This takes O(Logn)time
int i = returnIndex(s, lt, rt);

// Returning the maximum of following the three possible cases:
//   a) The maximum area in the left of the minimum value (excluding the minimum)
//   a) The maximum area in the right of the minimum value (excluding the minimum)
//   c) The maximum area including the minimum 
return max(findMaxAreaRec(s, lt, i - 1), findMaxAreaRec( s, i + 1, rt), (rt - lt + 1) * (hist[i]));
}

// The method for computing the max rect area
public int computeMaxArea( int s)
{
// Constructing the segment tree from the provided array. It takes O(n) time
constructSegTree(s);

// Using the utility method that uses recursion for finding the
// maximum area
return findMaxAreaRec(s, 0, s - 1);
}

// main method
public static void main(String[] argvs)
{
int[] arr = {7, 2, 6, 5, 6, 2, 7};
int s = arr.length;
hist = new int[s];
LargestRectArea1 obj = new LargestRectArea1();
hist = arr;
System.out.println("The maximum rectangular area is: " + obj.computeMaxArea(s));
}
}

输出

The maximum rectangular area is: 15

时间复杂度：在上面的程序中，时间复杂度取决于两件事：一是线段树，二是查找最大矩形面积。构建线段树所需的时间复杂度为 O(n)，查找最大矩形面积所需的时间复杂度为 O(log(n))。因此，时间复杂度变为 O(n) + O(n * log(n))，渐进时间复杂度变为 O(n * log(n))，其中 n 是输入数组中存在的元素总数。

如果我们比较以上两个程序，会发现后一个程序更优化，因为它解决问题所需的时间更少。但是，我们可以进一步优化它。让我们在以下方法中进行查看。

方法：使用栈

让我们看看使用栈查找矩形面积的算法。

步骤 1：创建一个栈用于压入和弹出元素。

步骤 2：从第一个条形开始，对每个条形 "histArr[j]" 执行以下任务，其中 'j' 从 0 到 s - 1。

如果栈为空或 histArr[ij] 比栈顶的条形长，则将 'j' 压入栈。
如果当前条形比栈顶的条形短，则不断从栈顶弹出条形，直到栈顶的条形较大。假设移除的条形是 histArr[top]。以 histArr[top] 作为最小条形计算矩形面积。对于 histArr[top]，'左索引'是栈中前一个（在 top 前面）的条形，而 '右索引'是 'j'（当前索引）。

步骤 3：如果栈中还有一些条形，则逐一弹出栈中的所有条形，并对每个移除的条形重复步骤 2(ii)。

文件名：LargestRectArea2.java

// import statement
import java.util.Stack;

public class LargestRectArea2
{
// The main method for computing the maximum rect area using the input
// histogram array with s bars
public int findMaxArea(int histArr[], int s)
{
// Creating an empty stack. The stack keeps indices of the histArr[] array
// The bars kept in the stack are in increasing order as per their heights
Stack<Integer> stk = new Stack<>();

int maxArea = 0; // Initializing the max area
int top; // for keeping the top of the stack
int areaWithTop; // for keeping the area with the bar at the top as the smallest bar

// Run through all bars of given histogram
int j = 0;
while (j < s)
{
// If the bar is longer than the bar present at the top of the stack, then push the bar to //the stack
if (stk.empty() || histArr[stk.peek()] <= histArr[j])
stk.push(j++);

// If the bar is lower than the top of the stack, then compute the area of the rectangle
// with the top of the stack as the min-height bar. 'j' is the right index for the 
// top and the element before the top in the stack is the 'left index'
else
{
top = stk.peek(); // storing the index at the top
stk.pop(); // popping the top

// computing the area with histArr[top] stack as the smallest bar
areaWithTop = histArr[top] * (stk.empty() ? j : j - stk.peek() - 1);

// updating the maximum area, if requried
if (maxArea < areaWithTop)
{
maxArea = areaWithTop;
}
}
}

// Now popping the left bars from the stack and computing the area with each bar
// that is popped as the bar that is smallest
while (stk.empty() == false)
{
top = stk.peek();
stk.pop();
areaWithTop = histArr[top] * (stk.empty() ? j : j - stk.peek() - 1);

if (maxArea < areaWithTop)
maxArea = areaWithTop;
}

return maxArea;

}

// Driver method to test above methods
public static void main(String[] args)
{
int[] histArr = {7, 2, 6, 5, 6, 2, 7};
int s = histArr.length; // computing size

// creating an object of the class LargestRectArea2
LargestRectArea2 obj = new LargestRectArea2();
System.out.println("The maximum rectangular area is: " + obj.findMaxArea(histArr, s));
}
}

输出

The maximum rectangular area is: 15

使用辅助数组

另一种方法是找到直方图中每个条形的前一个更小条形和后一个更小条形，这将通过两个辅助数组来实现。请参阅以下算法。

步骤 1：首先，我们采用两个辅助数组 leftSmaller[] 和 rightSmaller[]，并将它们分别初始化为负数和 n。

步骤 2：对于每个元素，我们在 rightSmaller[] 和 leftSmaller[] 数组中分别保留后一个更小元素和前一个更小元素的索引。这需要 O(n) 的时间。

步骤 3：对于每个条形，我们通过将第 j 个条形作为 leftSmaller[j] 和 rightSmaller[j] 范围内的最短条形来计算面积，并将其乘以 leftSmaller[j] 和 rightSmaller[j] 的差值。

步骤 4：可以通过比较每个条形的面积来计算最大面积。不同条形的面积在步骤 3 中计算。

文件名：LargestRectArea3.java

// import statement
import java.util.Stack;


public class LargestRectArea3
{

// method for finding the maximum rectangular area in the given histogram.
public int findMaxArea(int a[], int s)
{
// creating an empty stack here
Stack<Integer> stk = new Stack<>();

// we push a negative number to the stack as for some of the bars there is a possibility that the previous smaller 
// bar is absent in the input array. In our case it is -1.
stk.push(-1);
int maxArea = a[0];
// We declare the leftSmaller and the rightSmaller array of the size s and intializing them with -1 and s as their default value.
// leftSmaller[j] keeps the index of the previous smaller bar for the jth bar.
// rightSmaller[j] keeps the index of the next smaller bar for the jth bar.
int leftSmaller[] = new int[s];
int rightSmaller[] = new int[s];
for (int j = 0; j < s; j++)
{
leftSmaller[j] = -1;
rightSmaller[j] = s;
}

int j = 0;
while (j < s)
{
while(!stk.empty() && stk.peek() != -1 && a[j] < a[stk.peek()])
{
// if the current bar is shorter than the bar with the index kept on the top
// of the stack then, pop the top bar and keep the current bar index as the rightSmaller
// for the bar that is popped bar.
rightSmaller[stk.peek()] = (int)j;
stk.pop();
}
if(j > 0 && a[j] == a[(j - 1)])
{
// use this condition to escape the loop that is unnecessary to look for the leftSmaller.
// since the previous bar is the same as the current element, 
// the leftSmaller bar is the same for both, always.
leftSmaller[j] = leftSmaller[(int)(j - 1)];
}
else
{
// bar with the stored index at the top of the stack is always shorter
// than the current bar.
// Hence, the leftSmaller[j] will always be on stk.top().
leftSmaller[j] = stk.peek();
}
stk.push(j);
j = j + 1;
}


for(j = 0; j < s; j++)
{
// computing the area with every bar as the shortest bar in its range and then 
// do the comparison it with the previously computed area. Using this way
// one can get the maximum area from this.
maxArea = Math.max(maxArea, a[j] * (rightSmaller[j] - leftSmaller[j] - 1));
}

return maxArea;
}

// main method
public static void main(String argvs[])
{
int[] histArr = {7, 2, 6, 5, 6, 2, 7};
int size = histArr.length; // computing size

LargestRectArea3 obj = new LargestRectArea3();
System.out.println("The maximum rectangular area is: " + obj.findMaxArea(histArr, size));
}
}

输出

The maximum rectangular area is: 15

时间复杂度：最后两种方法的复杂度为 O(n)，其中 n 是数组中存在的元素总数。

下一主题Java 中的多边形数

Java 中直方图的最大矩形面积

直方图中的最大矩形面积是什么？

朴素方法

分治法

方法：使用栈

使用辅助数组

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中直方图的最大矩形面积

直方图中的最大矩形面积是什么？

朴素方法

分治法

方法：使用栈

使用辅助数组

相关帖子

Java 中的图像处理 - 亮度增强

ArrayList vs HashMap

Java 中的宏观数

命名两种 Java 程序类型

Java CloneNotSupportedException 及其示例

如何在 Java 中重写 tostring() 方法

如何在 Java 中分解日期和时间

Unary Operators in Java

Java 中 String、StringBuffer 和 StringBuilder 的区别

Java 购物账单程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器