LeetCode 84. 柱状图中最大的矩形
原题链接
困难
作者:
LangB
,
2020-11-05 10:55:44
,
所有人可见
,
阅读 274
暴力解法
class Solution {
public int largestRectangleArea(int[] heights) {
int res = 0;
for (int i = 0; i < heights.length; i++) {
int w = 1, h = heights[i], j = i;
while (--j >= 0 && heights[j] >= h) {
w++;
}
j = i;
while (++j < heights.length && heights[j] >= h) {
w++;
}
res = Math.max(res, h * w);
}
return res;
}
}
栈
class Solution {
public int largestRectangleArea(int[] heights) {
int[] temp = new int[heights.length + 2];
System.arraycopy(heights, 0, temp, 1, heights.length);;
Deque<Integer> stack = new ArrayDeque<>();
int res = 0;
for (int i = 0; i < temp.length; i++) {
while (!stack.isEmpty() && temp[i] < temp[stack.peek()]) {
int h = temp[stack.pop()];
res = Math.max(res, (i - stack.peek() - 1) * h);
}
stack.push(i);
}
return res;
}
}