由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 我也来问问LC的Maximal Rectangle
相关主题
有用java过Maximal Rectangle的judge large的吗?算法--一个MXN matrix (0's and 1's)内求最大 rectangle(1's)
求Leetcode OJ Maximal Rectangle的n^2解法这个histgram的最大面积问题
再问Maximal Rectangle的N^2解法Maximal Rectangle如果不要求是Rectangle就要简单得多
Maximal Rectangle O(mn) 解法 非 histogramLargest Rectangle in Histogram不同算法的复杂度
Maximal Rectangle TLE是指代码正确,但不是最优吗?问一道G家面试题
leetcode一道题总结一道题
Largest Rectangle in Histogram一道面试算法题
Question about Leetcode: Maximum rectangle直方图盛水最大容量问题
相关话题的讨论汇总
话题: int话题: res话题: lc话题: rectangle话题: maximal
进入JobHunting版参与讨论
1 (共1页)
i*****d
发帖数: 962
1
看了答案感觉不大好了解,自己单独写总是有bug,有大牛给解释解释吗?
w*******o
发帖数: 113
2
没有
l********r
发帖数: 221
3
参考递增单调栈思路
w*******o
发帖数: 113
4
这题是84题的一个小拓展,不过不是很容易想到。
84题就是说如果直方图的高度是递增的,我们就入栈他的index以计算宽度,如果下降
了,就弹栈清算无法拓展面积的bar。
代码如下:
public int largestRectangleArea(int[] heights) {
Stack st = new Stack<>();
int[] nums = Arrays.copyOf(heights, heights.length + 1);
int res = 0;
for (int i = 0; i < nums.length; i++) {
while (!st.empty() && nums[st.peek()] >= nums[i]) {
int h = nums[st.pop()];
int w = st.empty() ? i : i - 1 - st.peek();
res = Math.max(res, w * h);
}
st.push(i);
}
return res;
}
第85题就是按照每一排来构建这样一个直方图,然后不停调用以上函数来更新最大的面
积。

public int maximalRectangle(char[][] matrix) {
int m = matrix.length, n = m == 0 ? 0 : matrix[0].length, res = 0;
int[] dp = new int[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[j] = matrix[i][j] == '0' ? 0 : dp[j] + 1;
}
res = Math.max(res, largestRectangleArea(dp));
}
return res;
}
1 (共1页)
进入JobHunting版参与讨论
相关主题
直方图盛水最大容量问题Maximal Rectangle TLE是指代码正确,但不是最优吗?
max rectangle这个O(mn)的算法是不是对的?leetcode一道题
Google interview questionLargest Rectangle in Histogram
请问一道题--给一个正方形矩阵,每个元素要么黑色要么白色,请找出最大的纯色子矩阵Question about Leetcode: Maximum rectangle
有用java过Maximal Rectangle的judge large的吗?算法--一个MXN matrix (0's and 1's)内求最大 rectangle(1's)
求Leetcode OJ Maximal Rectangle的n^2解法这个histgram的最大面积问题
再问Maximal Rectangle的N^2解法Maximal Rectangle如果不要求是Rectangle就要简单得多
Maximal Rectangle O(mn) 解法 非 histogramLargest Rectangle in Histogram不同算法的复杂度
相关话题的讨论汇总
话题: int话题: res话题: lc话题: rectangle话题: maximal