공부공간

www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net N이 10만이기때문에 일반적인 모든구간을 탐색하는 N^2풀이시 시간초과를 만나게된다. 복잡도를 줄이기위해 어떤 직사각형을 생각해보면 그 높이는 입력으로 들어온 것들중 한개일 것이다. 너비는 적당한 구간일 것이고, 따라서 높이를 N개 탐색하는데, 구간에 대해서 최솟값을 반환해주는 함수가있다면, 높이를 최소부터 최대까지 탐색할수 있을것이다. 그러면 구간 점 ..