jingoshine, your WB had been refund, please check it out.# Stock
i*d
1 楼
看了答案感觉不大好了解，自己单独写总是有bug，有大牛给解释解释吗？
g*4
2 楼
对不起，pick销售时间已过。
w*o
3 楼
没有
j*e
4 楼
没事，下次再买
【在 g********4 的大作中提到】
: 对不起，pick销售时间已过。
【在 g********4 的大作中提到】
: 对不起，pick销售时间已过。
l*r
5 楼
参考递增单调栈思路
w*o
6 楼
这题是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;
}
84题就是说如果直方图的高度是递增的，我们就入栈他的index以计算宽度，如果下降
了，就弹栈清算无法拓展面积的bar。
代码如下：
public int largestRectangleArea(int[] heights) {
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;
}
相关阅读