i*****d
发帖数: 962 | 1 看了答案感觉不大好了解，自己单独写总是有bug，有大牛给解释解释吗？ | w*******o
发帖数: 113 | | l********r
发帖数: 221 | | 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;
} |
|
