-
Notifications
You must be signed in to change notification settings - Fork 0
/
largestRectangleArea_84.java
57 lines (52 loc) · 1.88 KB
/
largestRectangleArea_84.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
* 84. 柱状图中最大的矩形
难度
困难
505
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
*/
import java.util.Stack;
class Solution {
//单调栈解法
public int largestRectangleArea(int[] heights) {
Stack<Integer> stack = new Stack<>();
stack.push(-1);
int max = 0;
for (int i = 0; i < heights.length; i++) {
while (stack.peek() != -1 && heights[i] <= heights[stack.peek()]) {
//如果为-1,左侧都比其大
max = Math.max(max, heights[stack.pop()] * (i - stack.peek() - 1));
}
stack.push(i);
}
while (stack.peek() != -1) {
//右侧都比其大, 仍要考虑左边可达-1的情况, 故先pop,后peek
max = Math.max(max, heights[stack.pop()] * (heights.length - stack.peek() - 1));
}
return max;
}
//分治思想 Onlgn
// public int largestRectangleArea(int[] heights) {
// if (heights == null || heights.length == 0) {
// return 0;
// }
// return process(heights, 0, heights.length-1);
// }
// public int process(int[] heights, int start, int end) {
// if (start > end) {
// return 0;
// }
// if (start == end) {
// return heights[start];
// }
// int index = start;
// for (int i = start + 1; i <= end; i++) {
// if (heights[i] < heights[index]) {
// index = i;
// }
// }
// int max = heights[index] * (end - start + 1);
// return Math.max(process(heights, index + 1, end), Math.max(max, process(heights, start, index - 1)));
// }
}