怎么用C++求直方图中最大的矩形

引言

在计算机科学和算法设计中，直方图最大矩形问题是一个经典的问题。给定一个直方图，每个条形的高度代表一个非负整数，宽度为1，要求找到直方图中最大的矩形面积。这个问题在图像处理、数据分析和计算机视觉等领域有广泛的应用。

本文将详细介绍如何使用C++解决直方图最大矩形问题。我们将从问题的定义开始，逐步介绍不同的解决方法，并最终给出一个高效的C++实现。

问题定义

给定一个直方图，每个条形的高度为一个非负整数，宽度为1。要求找到直方图中最大的矩形面积。

例如，给定直方图 [2, 1, 5, 6, 2, 3]，最大的矩形面积为10，对应的矩形高度为5，宽度为2。

方法一：暴力法

思路

暴力法的思路是枚举所有可能的矩形，计算每个矩形的面积，然后找到最大的面积。

具体来说，对于每个条形，我们将其作为矩形的高度，然后向左右扩展，直到遇到比当前高度小的条形为止。这样，我们就可以得到以当前条形为高度的最大矩形面积。

实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int largestRectangleAreaBruteForce(vector<int>& heights) {
    int maxArea = 0;
    int n = heights.size();
    
    for (int i = 0; i < n; ++i) {
        int minHeight = heights[i];
        for (int j = i; j < n; ++j) {
            minHeight = min(minHeight, heights[j]);
            int area = minHeight * (j - i + 1);
            maxArea = max(maxArea, area);
        }
    }
    
    return maxArea;
}

int main() {
    vector<int> heights = {2, 1, 5, 6, 2, 3};
    cout << "最大矩形面积: " << largestRectangleAreaBruteForce(heights) << endl;
    return 0;
}

复杂度分析

• 时间复杂度：O(n^2)，其中n是直方图的长度。对于每个条形，我们需要遍历其后的所有条形。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

优缺点

• 优点：实现简单，容易理解。
• 缺点：时间复杂度较高，对于大规模数据不适用。

方法二：分治法

思路

分治法的思路是将直方图分成左右两部分，分别求解左右两部分的最大矩形面积，然后考虑跨越中间的最大矩形面积。

具体来说，我们首先找到直方图中的最小高度，然后以最小高度为基准，将直方图分成左右两部分。最大矩形面积要么在左半部分，要么在右半部分，要么跨越中间的最小高度。

实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int largestRectangleAreaDivideAndConquer(vector<int>& heights, int left, int right) {
    if (left > right) return 0;
    
    int minIndex = left;
    for (int i = left; i <= right; ++i) {
        if (heights[i] < heights[minIndex]) {
            minIndex = i;
        }
    }
    
    int area = heights[minIndex] * (right - left + 1);
    int leftArea = largestRectangleAreaDivideAndConquer(heights, left, minIndex - 1);
    int rightArea = largestRectangleAreaDivideAndConquer(heights, minIndex + 1, right);
    
    return max(area, max(leftArea, rightArea));
}

int largestRectangleAreaDivideAndConquer(vector<int>& heights) {
    return largestRectangleAreaDivideAndConquer(heights, 0, heights.size() - 1);
}

int main() {
    vector<int> heights = {2, 1, 5, 6, 2, 3};
    cout << "最大矩形面积: " << largestRectangleAreaDivideAndConquer(heights) << endl;
    return 0;
}

复杂度分析

• 时间复杂度：O(n log n)，其中n是直方图的长度。每次递归调用都会将问题规模减半，但在最坏情况下，每次都需要遍历整个直方图来找到最小高度。
• 空间复杂度：O(log n)，递归调用的深度为log n。

优缺点

• 优点：时间复杂度比暴力法有所改善。
• 缺点：在最坏情况下，时间复杂度仍然较高。

方法三：单调栈法

思路

单调栈法的思路是利用栈来维护一个递增的条形高度序列。对于每个条形，我们将其高度与栈顶元素的高度进行比较。如果当前条形的高度小于栈顶元素的高度，则弹出栈顶元素，并计算以栈顶元素为高度的最大矩形面积。

具体来说，我们遍历直方图中的每个条形，将其索引压入栈中。当遇到一个比栈顶元素小的条形时，我们弹出栈顶元素，并计算以该元素为高度的最大矩形面积。这个矩形的宽度为当前索引与栈顶元素索引的差值减1。

实现

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int largestRectangleAreaMonotonicStack(vector<int>& heights) {
    stack<int> s;
    heights.push_back(0); // 添加一个高度为0的条形，确保所有条形都被处理
    int maxArea = 0;
    int n = heights.size();
    
    for (int i = 0; i < n; ++i) {
        while (!s.empty() && heights[i] < heights[s.top()]) {
            int height = heights[s.top()];
            s.pop();
            int width = s.empty() ? i : (i - s.top() - 1);
            maxArea = max(maxArea, height * width);
        }
        s.push(i);
    }
    
    return maxArea;
}

int main() {
    vector<int> heights = {2, 1, 5, 6, 2, 3};
    cout << "最大矩形面积: " << largestRectangleAreaMonotonicStack(heights) << endl;
    return 0;
}

复杂度分析

• 时间复杂度：O(n)，其中n是直方图的长度。每个条形最多被压入和弹出栈一次。
• 空间复杂度：O(n)，栈的大小最多为n。

优缺点

• 优点：时间复杂度最低，适用于大规模数据。
• 缺点：实现相对复杂，需要理解单调栈的原理。

方法四：动态规划法

思路

动态规划法的思路是利用两个数组left和right来记录每个条形向左和向右扩展的最大宽度。然后，对于每个条形，我们可以计算以该条形为高度的最大矩形面积。

具体来说，left[i]表示第i个条形向左扩展的最大宽度，right[i]表示第i个条形向右扩展的最大宽度。然后，最大矩形面积为heights[i] * (right[i] - left[i] + 1)。

实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int largestRectangleAreaDynamicProgramming(vector<int>& heights) {
    int n = heights.size();
    if (n == 0) return 0;
    
    vector<int> left(n), right(n);
    
    // 计算每个条形向左扩展的最大宽度
    left[0] = 0;
    for (int i = 1; i < n; ++i) {
        int p = i - 1;
        while (p >= 0 && heights[p] >= heights[i]) {
            p = left[p] - 1;
        }
        left[i] = p + 1;
    }
    
    // 计算每个条形向右扩展的最大宽度
    right[n - 1] = n - 1;
    for (int i = n - 2; i >= 0; --i) {
        int p = i + 1;
        while (p < n && heights[p] >= heights[i]) {
            p = right[p] + 1;
        }
        right[i] = p - 1;
    }
    
    // 计算最大矩形面积
    int maxArea = 0;
    for (int i = 0; i < n; ++i) {
        maxArea = max(maxArea, heights[i] * (right[i] - left[i] + 1));
    }
    
    return maxArea;
}

int main() {
    vector<int> heights = {2, 1, 5, 6, 2, 3};
    cout << "最大矩形面积: " << largestRectangleAreaDynamicProgramming(heights) << endl;
    return 0;
}

复杂度分析

• 时间复杂度：O(n)，其中n是直方图的长度。每个条形最多被访问两次。
• 空间复杂度：O(n)，需要两个额外的数组来存储每个条形的左右扩展宽度。

优缺点

• 优点：时间复杂度较低，适用于大规模数据。
• 缺点：实现相对复杂，需要理解动态规划的原理。

结论

本文介绍了四种不同的方法来解决直方图最大矩形问题：暴力法、分治法、单调栈法和动态规划法。每种方法都有其优缺点，适用于不同的场景。

• 暴力法：实现简单，但时间复杂度较高，适用于小规模数据。
• 分治法：时间复杂度有所改善，但在最坏情况下仍然较高。
• 单调栈法：时间复杂度最低，适用于大规模数据，但实现相对复杂。
• 动态规划法：时间复杂度较低，适用于大规模数据，但实现相对复杂。

在实际应用中，单调栈法和动态规划法是最常用的方法，因为它们的时间复杂度最低，适用于大规模数据。如果你对算法的实现有较高的要求，建议使用单调栈法或动态规划法。

参考代码

以下是使用单调栈法的完整C++代码：

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int largestRectangleAreaMonotonicStack(vector<int>& heights) {
    stack<int> s;
    heights.push_back(0); // 添加一个高度为0的条形，确保所有条形都被处理
    int maxArea = 0;
    int n = heights.size();
    
    for (int i = 0; i < n; ++i) {
        while (!s.empty() && heights[i] < heights[s.top()]) {
            int height = heights[s.top()];
            s.pop();
            int width = s.empty() ? i : (i - s.top() - 1);
            maxArea = max(maxArea, height * width);
        }
        s.push(i);
    }
    
    return maxArea;
}

int main() {
    vector<int> heights = {2, 1, 5, 6, 2, 3};
    cout << "最大矩形面积: " << largestRectangleAreaMonotonicStack(heights) << endl;
    return 0;
}

希望本文对你理解和使用C++解决直方图最大矩形问题有所帮助！