logo标签列表

最大化直方图下的矩形面积

algorithm
77

我有一个高度为整数且宽度恒定为1的直方图。我想最大化直方图下面的矩形区域。 例如：

 _
| |
| |_ 
|   |
|   |_
|     |

答案是6，即使用col1和col2相乘得到。

我知道O(n^2)的暴力方法，但我想要一个O(n log n)的算法。我尝试考虑最大递增子序列的动态规划算法（O(n log n)），但是卡住了。我应该使用分治算法吗？

PS：有足够声望的人请删除divide-and-conquer标签，如果没有这样的解决方案。

mho的评论之后：我的意思是适合完全适配的最大矩形区域。（感谢j_random_hacker澄清 :)）。

2
如果列的高度分别为3、2、1，则如何使面积为3*2！因此，面积=3+2+1=6。 另外，最大化什么？你可以改变什么？问题还不清楚。 - Om Deshmane
11
我认为“最大化矩形面积”指的是“找到完全适合直方图下方的最大矩形的面积”。 - j_random_hacker
你可以在这里找到很多解决方案（http://blog.csdn.net/arbuckle/archive/2006/05/06/710988.aspx），包括O(n log n)和O(n)的算法。 - IVlad
1
官方网址为http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html。 - freestyler
我在这里找到了一个图形化解释O(n)解决方案Largest_Rectangle_In_Histogram。 - ktime
13个回答
0

我在一次面试中遇到了这个问题。试图解决它，结果观察到以下几点 -

  1. 需要检查连续的左侧元素是否大于当前元素
  2. 需要检查连续的右侧元素是否大于当前元素
  3. 计算面积 (左侧最大元素数 + 右侧最大元素数 + 1) * 当前元素
  4. 如果计算出的面积大于maxArea，则检查并替换现有的maxArea

以下是实现上述伪代码的JS代码

function maxAreaCovered(arr) {
    let maxArea = 0;
    for (let index = 0; index < arr.length; index++) {
        let l = index - 1;
        let r = index + 1;
        let maxEleCount = 0
        while (l > -1) {
            if (arr[l] >= arr[index]) {
                maxEleCount++;
            } else {
                break;
            }
            l--;
        }
        while (r < arr.length) {
            if (arr[r] >= arr[index]) {
                maxEleCount++;
            } else {
                break;
            }
            r++;
        }
        let area = (maxEleCount + 1) * arr[index];
        maxArea = Math.max(area, maxArea);
    }
    return maxArea
}

console.log(maxAreaCovered([6, 2, 5, 4, 5, 1, 6]));

0

-->

{{链接1：Python-3}}

    a=[3,4,7,4,6]
    a.sort()
    r=0
    for i in range(len(a)):
        if a[i]* (n-1) > r:
            r = a[i]*(n-i)
    print(r)

输出：

16

-1

您可以使用O(n)方法，该方法使用堆栈来计算直方图下的最大面积。

long long histogramArea(vector<int> &histo){
   stack<int> s;
   long long maxArea=0;
   long long area= 0;
   int i =0;
   for (i = 0; i < histo.size();) {
    if(s.empty() || histo[s.top()] <= histo[i]){
        s.push(i++);
    }
    else{
        int top = s.top(); s.pop();
        area= histo[top]* (s.empty()?i:i-s.top()-1);
        if(area >maxArea)
            maxArea= area;
    }
  }
  while(!s.empty()){
    int top = s.top();s.pop();
    area= histo[top]* (s.empty()?i:i-s.top()-1);
    if(area >maxArea)
        maxArea= area;
 }
 return maxArea;
}

关于此问题的解释可以在这里阅读 http://www.geeksforgeeks.org/largest-rectangle-under-histogram/

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接