240729 히스토그램에서 가장 큰 직사각형

private static int[] histogram;

public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st;
	StringBuilder sb = new StringBuilder();

	while (true) {
		st = new StringTokenizer(br.readLine(), " ");
		int n = Integer.parseInt(st.nextToken());

		if (n == 0) {
			break;
		}

		histogram = new int[n];
		for (int i = 0; i < n; i++) {
			histogram[i] = Integer.parseInt(st.nextToken());
		}

		sb.append(getMaxArea(n)).append('\n');
	}
	System.out.print(sb.toString());
	br.close();
}

private static long getMaxArea(int len) {
	int[] stack = new int[len];
	int size = 0;
	int top = -1;
	long maxArea = 0;

	for (int i = 0; i < len; i++) {
		while (size > 0 && histogram[stack[top]] >= histogram[i]) {
			int height = histogram[stack[top--]];
			size--;
			long width = size == 0 ? i : i - 1 - stack[top];
			maxArea = Math.max(maxArea, height * width);
		}
		stack[++top] = i;
		size++;
	}

	while (size > 0) {
		int height = histogram[stack[top--]];
		size--;
		long width = size == 0 ? len : len - 1 - stack[top];
		maxArea = Math.max(maxArea, width * height);
	}

	return maxArea;
}

출처:https://www.acmicpc.net/problem/6549