Largest Rectangle in Histogram
- 문제
- 주어진 그래프에서 가장 넓은 직사각형의 넓이를 구하라
- 생각해볼 수 있는 것
- 가장 높은 막대를 기준으로 넓이를 측정
- 낮은 막대가 많고 길이가 긴 경우에는 성립하지 않는다
- 가장 낮은 것을 기준으로 넓이 측정 (0 제외)
- 높은 막대가 많고 길이가 짧은 경우에는 성립하지 않는다
중간 길이의 막대가 기준이 되어 가장 넓은 직사각형이 될 수 있고, 가장 낮은 막대가 기준이 되어 가장 넓은 직사각형이 될 수 있고, 가장 높은 막대가 기준이 되어 가장 넓은 직사각형이 될 수 있다
모든 경우를 조사해야 가장 넓은 직사각형을 알 수 있다 n은 10만이기 때문에 n^log(n) 안에 풀어야 한다
- 가장 높은 막대를 기준으로 넓이를 측정
- 풀이
- 막대의 길이와 인덱스를 스택에 삽입
- 핵심 : 스택은 항상 오름차순으로 유지 (맨 위에 있는 막대의 높이보다, 낮은 막대를 발견한다면 스택 재정렬)
- 낮은 막대가 들어왔다면 더 이상 넓이를 늘릴 수 없다
- 스택에 지금 들어온 막대보다 큰 막대들은 전부 POP 해주면서 넓이를 측정한다
- 지금까지 오름차순이었기에 먼저 들어온 막대들은 현재 인덱스까지 직사각형을 만들 수 있다
- 더 이상 낮은 막대가 없다면 가장 최근에 삭제된 인덱스를 현재 들어오는 막대의 인덱스에 대입
- 더 이상 낮은 막대가 없다는 뜻은 삭제된 인덱스까지는 직사각형을 만들 수 있다는 뜻
- 모든 막대를 검사하고, 스택에 남아있는 막대가 있다면 그래프의 길이만큼 넓이 측정
- 가장 큰 값 리턴
Code
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
import java.util.*;
class Pair {
int index;
int num;
public Pair(int index, int num) {
this.index = index;
this.num = num;
}
}
class Solution {
public int largestRectangleArea(int[] heights) {
Stack<Pair> stack = new Stack<>();
int answer = 0;
for(int i=0;i<heights.length;i++) {
int now = heights[i];
if(stack.size() == 0)
stack.push(new Pair(i, now));
else {
Pair top = stack.peek();
if(top.num < now)
stack.push(new Pair(i, now));
else {
int lastIndex = 0;
while(!stack.isEmpty()) {
lastIndex = top.index;
top = stack.pop();
if(top.num < now) {
stack.push(top);
break;
}
answer = Math.max((i - top.index) * top.num, answer);
}
if(stack.isEmpty())
stack.push(new Pair(top.index, now));
else
stack.push(new Pair(lastIndex, now));
}
}
}
while(!stack.isEmpty()) {
Pair top = stack.pop();
answer = Math.max((heights.length - top.index) * top.num, answer);
}
return answer;
}
}
