[BOJ] 6549번: 히스토그램에서 가장 큰 직사각형

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

분할 정복 카테고리에 들어가있긴 하지만 분할 정복 대신 스택을 이용해 O(N)으로 풀이할 수가 있습니다. 풀이에서의 핵심은 이전의 직사각형보다 작은 직사각형이 들어왔을 경우 이전 직사각형들의 정보를 굳이 완전하게 가져가지 않아도 괜찮다는 것입니다.

예를 들어 높이 3 4 2인 직사각형에서 스택을 3->4->2 순서로 채워나갈 때, 2가 들어온 시점에는 굳이 앞의 높이가 3, 4인지를 알 필요 없이 그냥 높이가 2인 직사각형이 3개 있다고 생각해도 상관이 없다는 의미입니다.

스택에는 높이와 직사각형의 시작 위치를 저장하고, 직사각형의 높이가 증가하도록 원소를 쌓아나갑니다.  스택에서 원소를 빼게 될 때 넓이의 최댓값을 갱신합니다. 자세한건 코드를 참고해주세요.

https://github.com/encrypted-def/BOJ/blob/master/6549.cpp