LeetCode 84. Largest Rectangle in Histogram

最新推荐文章于 2025-03-31 12:56:12 发布

Allenlzcoder

最新推荐文章于 2025-03-31 12:56:12 发布

阅读量305

点赞数

分类专栏： LeetCode练习题文章标签： LeetCode 84. Largest Rectangle

本文链接：https://blog.csdn.net/Allenlzcoder/article/details/80722009

版权

LeetCode练习题专栏收录该内容

168 篇文章

订阅专栏

本文探讨LeetCode 84题“柱状图中最大的矩形”的两种解法，一种为循环嵌套动态规划，另一种为局部峰值遍历算法。分析了这两种方法的优缺点，并给出具体实现代码。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

LeetCode 84. Largest Rectangle in Histogram

Solution1：我的答案
循环里头套了一个动态规划，缺点是当heights个数或最大高度多高时会很耗时间！！！运行至第37个case时超时了….
还是记录一下。。。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        if (n == 0) return 0;
        else if (n == 1) return heights[0];
        int height_max = INT_MIN;
        set<int> res;
        for (int i = 0; i < heights.size(); i++) height_max = max(height_max, heights[i]);
        for (int i = 0; i <= height_max; i++) {
            int temp = 0, temp_max = INT_MIN;
            vector<int> dp(n, 0);
            for (int j = 0; j < n; j++) {//DP，思路与在0、1组成的字符串里求最长1的串思路相同
                if (heights[j] < i)
                    temp = 0;
                else {
                    temp += i;
                    dp[j] = temp;
                }
                temp_max = max(temp_max, dp[j]);
            }
            res.insert(temp_max);
        }
        return *(--res.end());
    }
};

Solution2：
参考网址：http://www.cnblogs.com/grandyang/p/4322653.html
每找到一个局部峰值，然后向前遍历所有的值，算出共同的矩形面积，每次对比保留最大值。
相当于只在每个峰值和下坡路上遍历，按理说复杂度是 $O(n^2)$ 。但是确实很快而且可以AC。。。

class Solution {
public:
    int largestRectangleArea(vector<int>& height) {
        int res = 0;
        for (int i = 0; i < height.size(); ++i) {
            if (i + 1 < height.size() && height[i] <= height[i + 1]) {//若把这个判断条件去掉，则是暴力算法复杂度是O(n^2)，只有最后一个case无法AC
                continue;
            }
            int minH = height[i];
            for (int j = i; j >= 0; --j) {
                minH = min(minH, height[j]);
                int area = minH * (i - j + 1);
                res = max(res, area);
            }
        }
        return res;
    }
};