[伯俊]6549号ヒーストロ最大の矩形/Java,Python
Baekjoon Online Judge
algorithm practice
-問題を逐次解く
20.分割征服
再帰的なアルゴリズムを応用し,分割征服を学ぶ.
Java/Python
9.ヒストグラムで最大の長方形
6549号
ヒストグラムで最大の矩形の問題を探します.分割征服で解くこともできるし、スタックで解くこともできる.
この問題は、ヒストグラムで最も広い矩形を得るためにプログラムを作成することです.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Stack;
class Main {
static int[] arr;
static int N;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
while(true){
st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
if(N == 0)
break;
arr = new int[N];
for(int i=0; i < N; i++)
arr[i] = Integer.parseInt(st.nextToken());
System.out.println(getMax(0, N - 1));
}
}
private static long getMax(int left, int right){
if(left == right) return arr[left];
int mid = (left + right) / 2;
// 두 구간으로 나누어, 둘 중 큰 넓이를 반환
long ret = Math.max(getMax(left, mid), getMax(mid+1, right));
int start = mid;
int end = mid+1;
// mid 기준 양쪽으로 너비 2만큼 겹치는 직사각형
long height = (long)Math.min(arr[start], arr[end]);
ret = (long)Math.max(ret, height*2);
// 범위를 벗어나기 전까지 확장
while(left < start || end < right){
// 왼쪽 범위를 넘지 않은 경우
if(left < start && end < right){
// 높이가 높은 쪽으로
if(arr[start -1] < arr[end+1])
height = (long)Math.min(height, arr[++end]);
else
height = (long)Math.min(height, arr[--start]);
}
else if(left < start){
// 오른쪽 범위를 넘은 경우 왼쪽으로만
height = (long)Math.min(height, arr[--start]);
}
else if(end < right){
// 왼쪽 범위를 넘은 경우 오른쪽으로만
height = (long)Math.min(height, arr[++end]);
}
ret = Math.max(ret, height*(end-start+1));
}
return ret;
}
}
import sys
def getMax(l, r):
if l == r:
return h[l]
else:
mid = (l + r) // 2
start = mid
end = mid + 1
height = min(h[start], h[end])
tmp = height * 2
cnt = 2
while True:
if (h[start] == 0 or start == l) and (h[end] == 0 or end == r):
break
elif h[start] == 0 or start == l:
if h[end + 1] < height:
height = h[end + 1]
end += 1
elif h[end] == 0 or end == r:
if h[start - 1] < height:
height = h[start - 1]
start -= 1
else:
if h[start - 1] > h[end + 1]:
if h[start - 1] < height:
height = h[start - 1]
start -= 1
else:
if h[end + 1] < height:
height = h[end + 1]
end += 1
cnt += 1
tmp = max(tmp, height * cnt)
return(max(getMax(l, mid), getMax(mid + 1, r), tmp))
while True:
h = list(map(int, sys.stdin.readline().split()))
if h[0] == 0:
break
print(getMax(1, len(h) - 1))
Reference
この問題について([伯俊]6549号ヒーストロ最大の矩形/Java,Python), 我々は、より多くの情報をここで見つけました https://velog.io/@jini_eun/백준-6549번-히스트로그램에서-가장-큰-직사각형-Java-Pythonテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol