[伯俊]6549号ヒーストロ最大の矩形/Java,Python


Baekjoon Online Judge


algorithm practice


-問題を逐次解く


20.分割征服


再帰的なアルゴリズムを応用し,分割征服を学ぶ.
Java/Python

9.ヒストグラムで最大の長方形


6549号
ヒストグラムで最大の矩形の問題を探します.分割征服で解くこともできるし、スタックで解くこともできる.

この問題は、ヒストグラムで最も広い矩形を得るためにプログラムを作成することです.
  • Java
  • 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;
    	}
    }
  • Python
  • 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))