LeetCode 84 Largest Rectangle in Histogram
题目分析
https://leetcode.com/problems/largest-rectangle-in-histogram/
这是一道 Hard 题。
实际上我们要找的就是两个端点而已。
双指针的话，遍历方式：
- 两个指针同向
- 两个指针相向
- 两个指针背向
两个指针同向（暴力遍历法）
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 一个？
两个指针背向
背向从哪里开始呢？可以先排序：
- 降序排序，从较大值开始；
- 升序排序，从较小值开始。
动态规划法
动态规划法的关键即状态转移方程，首先我们要搞清楚用什么当状态。 这里显然可以直接用两个端点的位置。
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 要高，那可以利用，要低的话要怎么利用呢？
啊，貌似不行欸。
利用已计算值进行跳跃
这样想，最终的矩形的顶部必然和某个高度保持一致，所以我们只需要对每个 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;
}
};