LeetCode 84 Largest Rectangle in Histogram

Tag: 数组类问题 LeetCode Posted on 2021-06-17 10:43:03 Edited on 2022-03-05 15:11:14 Views: 433

题目分析

https://leetcode.com/problems/largest-rectangle-in-histogram/

这是一道 Hard 题。

实际上我们要找的就是两个端点而已。

双指针的话,遍历方式:

  1. 两个指针同向
  2. 两个指针相向
  3. 两个指针背向

两个指针同向(暴力遍历法)

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int ans = 0;
        for(int l=0;l<heights.size();l++) {
            int minHeight = INT_MAX;
            for(int r=l;r<heights.size();r++) {
                minHeight = min(minHeight, heights[r]);
                ans = max(ans, minHeight * (r - l + 1));
            }
        }
        return ans;
    }
};

时间复杂度 O(n^2),88 / 96 test cases passed,果然 TLE。

两个指针相向

主要的好处是,宽度是递减的,有助于我们排除非最优解。

主要障碍是我们不知道内部高度的最小值,对于这一点,可以先排序存下来,之后遇到一个 mark 一个?

两个指针背向

背向从哪里开始呢?可以先排序:

  1. 降序排序,从较大值开始;
  2. 升序排序,从较小值开始。

动态规划法

动态规划法的关键即状态转移方程,首先我们要搞清楚用什么当状态。 这里显然可以直接用两个端点的位置。

cache 里除了存其最大值也要存一下 minHeight。

class Solution {
public:
    vector<vector<int>> dp;
    vector<vector<int>> minHeights;
    vector<int> heights;
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        vector<vector<int>> minHeights(n, vector<int>(n, INT_MAX));
        this->heights = heights;
        this->dp = dp;
        this->minHeights = minHeights;
        return helper(0, n-1);
    }
    
    int helper(int l, int r) {
        if (dp[l][r] != 0) return dp[l][r];
        if (l == r) {
            dp[l][r] = heights[l];
            minHeights[l][r] = heights[l];
            return dp[l][r];
        }
        int width = r - l + 1;
        int v1 = helper(l+1, r);
        int v2 = helper(l, r-1);
        int minHeight = min(minHeights[l+1][r], heights[l]);
        minHeights[l][r] = minHeight;
        dp[l][r] = max(minHeight * width, max(v1, v2));
        return dp[l][r];
    }
};

离谱,还是 TLE,而且是 87 / 96 test cases passed,比暴力法还差。。。


以上为 21 年的笔记。

动态规划法(一维的状态)

有没有注意到暴力遍历法也就 O(n^2) 而已,这说明我们需要找到更低复杂度的解法。

我们令 dp[i] 表示以第 i 个开始的矩阵的最大矩形。

状态转移是怎么样的呢?如果当前高度比 i+1 要高,那可以利用,要低的话要怎么利用呢?

啊,貌似不行欸。

利用已计算值进行跳跃

https://leetcode.com/problems/largest-rectangle-in-histogram/discuss/28902/5ms-O(n)-Java-solution-explained-(beats-96)

这样想,最终的矩形的顶部必然和某个高度保持一致,所以我们只需要对每个 heights[i],求出以其为高的最大矩形, 再从中选最大即可。

问题转换为如何高效求出 heights[i] 左边最远的不小于其高度的元素的索引(右边同理)。

暴力解是 O(n^2),但是通过利用已计算的值快速跳跃可以削减计算量:

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        vector<int> left = heights, right = heights;
        left[0] = -1;  // the idx of the first element that lower then current
        for (int i = 1; i < heights.size(); i ++) {
            int t = i - 1;
            while (t >= 0 && heights[t] >= heights[i]) {
                t = left[t];
            }
            left[i] = t;
        }
        right[heights.size()-1] = heights.size();
        for (int i = heights.size() - 2; i >= 0; i --) {
            int t = i + 1;
            while (t < heights.size() && heights[t] >= heights[i]) {
                t = right[t];
            }
            right[i] = t;
        }
        int ans = 0;
        for (int i = 0; i < heights.size(); i ++) {
            ans = max(ans, heights[i] * (right[i] - left[i] - 1));
        }
        return ans;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/