c++ - 直方图中最大的矩形

我正在研究以下算法难题，这是详细的问题说明。

找到直方图的最大矩形；例如，给定直方图= [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;
    }
};

最佳答案

满足以下条件时，会发生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。

在这种情况下，这两种方法将始终保持一致。在所有其他情况下，他们将不同意，并会产生不同的结果。

您可以通过在i循环底部的每次迭代打印nextTop，(i - top)，(i - nextTop - 1)，result和while的值来查看正在发生的情况。将{5, 4, 3, 2, 1}替换为{ 1, 2, 3, 4, 5}时， vector i-nextTop-1可以正常工作，但i-top不能正常工作。

算法原理

外部for循环一次遍历直方图元素。元素从左到右被压入堆栈，进入while循环后，堆栈顶部包含当前元素之前(或左侧)的元素。 (这是因为当前元素在循环回到顶部之前就被推到了for循环底部的堆栈上。)

当算法确定已经考虑了包括该元素的最佳解决方案时，该元素将从while循环中的堆栈中弹出。

内部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的先前值中的较大者。