-
Notifications
You must be signed in to change notification settings - Fork 11
/
LargestRectangle.java
49 lines (39 loc) Β· 1.36 KB
/
LargestRectangle.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
// https://www.hackerrank.com/challenges/largest-rectangle/problem
package stacks;
import helper.Input;
import java.util.Stack;
public class LargestRectangle {
public static void main(String[] args) {
int[] array = Input.getArray();
long area = maxArea(array);
System.out.println(area);
}
private static long maxArea(int[] heights) {
Stack<Info> stack = new Stack<>();
long area = 0;
for (int index = 0 ; index < heights.length ; index++) {
while (!stack.isEmpty() && (heights[index] < stack.peek().element)) {
Info top = stack.pop();
area = Math.max(area, calculateArea(top.element, stack, index));
}
stack.push(new Info(heights[index], index));
}
while (!stack.isEmpty()) {
Info top = stack.pop();
area = Math.max(area,calculateArea(top.element, stack, heights.length));
}
return area;
}
private static long calculateArea(int element, Stack<Info> stack, int index) {
int startIndex = stack.isEmpty() ? -1 : stack.peek().index;
return element * (index - startIndex - 1);
}
private static class Info {
int element;
int index;
Info(int element, int index) {
this.element = element;
this.index = index;
}
}
}