直方图中的最大矩形面积

Question

直方图中的最大矩形面积

10

我正在解决以下算法难题，以下是详细的问题陈述。

找到柱状图中最大的矩形; 例如，给定柱状图 = [2,1,5,6,2,3]，该算法应返回10。

我正在处理以下版本的代码。我的问题是，我认为i-nextTop-1可以被i-top替换，但在一些测试用例中（例如[2,1,2]），它们产生不同的结果（i-nextTop-1总是生成正确的结果）。我认为逻辑上它们应该是相同的，并想知道在什么情况下i-nextTop-1不等于i-top。

class Solution {
public:
    int largestRectangleArea(vector<int>& height) {
        height.push_back(0);
        int result=0;
        stack<int> indexStack;
        for(int i=0;i<height.size();i++){
            while(!indexStack.empty()&&height[i]<height[indexStack.top()]){
                int top=indexStack.top();
                indexStack.pop(); 
                int nextTop=indexStack.size()==0?-1:indexStack.top();
                result=max((i-nextTop-1)*height[top],result);
            }
            indexStack.push(i);
        }
        return result;
    }
};

- Lin Ma

这是一个在线的谜题吗？你能提供一个网址吗？ - fjardon

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- sifferman · Accepted Answer

当以下条件成立时，i-nextTop-1 != i-top的情况会发生：

nextTop != top-1

只需简单地重新排列不等式i-nextTop-1 != i-top就可以看出这一点。

理解这种情况发生的关键在于您代码中以下行中定义了nextTop的值：

int nextTop = indexStack.size() == 0 ? -1 : indexStack.top();

在这里，你说如果indexStack为空（在上一行代码的pop()之后），则将nextTop设置为-1；否则将nextTop设置为当前的indexStack.top()。

因此，只有当nextTop == top-1时，才会发生以下情况：

indexStack为空且top == 0，或者
indexStack.top() == top - 1。

在这些情况下，两种方法始终会产生相同的结果。在其他所有情况下，它们将不同，从而产生不同的结果。

您可以通过在while循环底部打印每次迭代的i、nextTop、(i-top)、(i-nextTop-1)和result的值来查看发生的情况。向量{5, 4, 3, 2, 1}运作良好，但是{1, 2, 3, 4, 5}不行，当将i-nextTop-1替换为i-top。

算法理论

外层for循环逐个迭代直方图元素。元素从左到右推入堆栈，在进入while循环时，堆栈顶部包含当前元素之前（或靠左的）的元素。（这是因为在for循环底部将当前元素推入堆栈，在返回顶部之前。）

在算法确定已经考虑了包括该元素的最佳解决方案时，就会从堆栈中弹出一个元素。

内部的while循环会一直迭代，只要height[i] < height[indexStack.top()]，也就是说，只要当前元素的高度小于堆栈上面的元素的高度。

在每次while循环的开始，堆栈上的元素代表当前元素左侧的所有连续元素，这些元素大于当前元素。

这使得算法能够计算包括当前元素和左侧所有元素的最大矩形的面积。这个计算是在以下两行代码中完成的：

int nextTop = indexStack.size() == 0 ? -1 : indexStack.top();
result = max((i - nextTop - 1) * height[top], result);

变量i是当前直方图元素的索引，表示当前正在计算的矩形的右侧边缘。

变量nextTop表示矩形的左侧边缘的索引。

表达式(i - nextTop - 1)表示矩形的水平宽度。height[top]是矩形的垂直高度，因此result是这两个术语的乘积。

每个新的result都是新计算和先前result值中较大的一个。