Largest Rectangle in Histogram

직사각형은 start부터 end까지 이어진 막대들의 구간을 덮으며, 높이는 구간에서 가장 낮은 막대의 높이로 제한됩니다. 그러니 모든 구간을 시도해 보세요. start를 고정한 다음, end를 한 번에 막대 하나씩 늘리고 지금까지 확인한 가장 낮은 높이를 계속 기록하세요. 해당 구간에서 가장 넓은 직사각형의 넓이는 lowest × (end-start+1)입니다.

[2, 5, 6, 3, 4, 1]에서 5부터 시작해 보세요. 구간별 넓이는 5 × 1 = 5이고, 6을 포함하면 5 × 2 = 10입니다. 그다음 3이 포함되면 3 × 3 = 9, 4를 포함하면 3 × 4 = 12, 1을 포함하면 1 × 5 = 5가 됩니다. 정답은 12입니다. 구간이 늘어날 때마다 lowest를 갱신하면 각 단계가 O(1)에 처리되므로, 최솟값을 찾기 위해 구간을 다시 훑을 필요가 없습니다.

모든 직사각형은 어떤 구간을 덮으며, 고정된 구간에 들어갈 수 있는 가장 높은 직사각형의 높이는 정확히 가장 낮은 막대의 높이와 같으므로 이 방법은 정확합니다. 하지만 n(n+1)/2개의 구간을 모두 살펴보므로 느립니다. 막대가 2 × 10^4개라면 약 2 × 10^8개이며, 이 개수는 막대의 높이와는 전혀 관계가 없습니다. 대부분의 구간은 끝에 도달하기 훨씬 전에 낮은 막대 때문에 더 이상 늘릴 수 없지만, 무차별 대입 방식은 그래도 계속 구간을 늘립니다.

검색 방향을 바꿔 보세요. 가장 큰 직사각형에서는 그 아래에 있는 막대 중 적어도 하나의 높이가 직사각형의 높이와 정확히 같습니다. 그렇지 않다면 직사각형을 더 높일 수 있습니다. 따라서 답은 모든 막대 i에 대해 높이가 정확히 heights[i]이고 가능한 한 넓게 펼쳐지는 직사각형 중 최댓값입니다. 양쪽에서 높이가 더 낮은 막대를 만날 때까지 펼쳐집니다. 그 인덱스를 left[i]와 right[i]라고 하며, 그런 막대가 없으면 -1과 n을 사용합니다. 직사각형은 그 사이에 있는 막대만 포함하므로 너비는 right[i]-left[i]-1입니다. 이렇게 하면 후보가 n²/2개가 아니라 n개입니다.

모든 막대에 대해 left[i]를 찾으려면, 스택 아래쪽에서 위쪽으로 갈수록 높이가 엄격히 증가하도록 인덱스를 쌓으면서 왼쪽에서 오른쪽으로 훑습니다. 막대 i가 오면 그 막대의 높이가 heights[i] 이상인 인덱스를 모두 꺼냅니다. 그 막대들은 i의 가장 가까운 더 낮은 막대일 수 없고, 그 뒤에 오는 어떤 막대의 가장 가까운 더 낮은 막대일 수도 없습니다. i가 더 가깝고 높이도 더 낮지 않기 때문입니다. 맨 위에 남은 항목이 왼쪽에서 가장 가까운 더 낮은 막대입니다. 그런 다음 i를 넣습니다. 오른쪽에서 왼쪽으로 같은 과정을 수행하면 right[i]를 구할 수 있습니다.

[2, 5, 6, 3, 4, 1]의 경우 두 번의 탐색 결과는 left = [-1, 0, 1, 0, 3, -1]과 right = [5, 3, 3, 5, 5, 6]입니다. 인덱스 3에 있는 높이 3의 막대는 인덱스 0의 높이 2인 막대와 인덱스 5의 높이 1인 막대에 막히므로, 그 직사각형의 넓이는 3 × (5-0-1) = 12입니다. 높이 6인 막대는 양옆의 막대에 막혀 6 × 1만 만들 수 있습니다.

각 인덱스는 각 탐색에서 한 번씩만 스택에 들어가고 최대 한 번만 꺼내지므로, 막대 하나가 여러 인덱스를 꺼내더라도 두 탐색 모두 O(n)입니다. 추가 배열 두 개가 필요합니다.

왼쪽에서 오른쪽으로 한 번 훑으면 이미 모든 오른쪽 경계를 확인하지만, 이를 버립니다. 막대 i가 막대 t를 팝할 때 heights[i]는 heights[t]보다 크지 않으므로, i는 t의 직사각형이 오른쪽에서 끝나는 위치입니다. 그리고 스택에서 t 바로 아래에 남은 인덱스는 직사각형이 왼쪽에서 끝나는 위치입니다. 그러므로 팝하는 순간 직사각형의 크기를 계산합니다. heights[t] × (i - below - 1)이며, 여기서 below는 스택의 새로운 맨 위 항목이고, 스택이 이제 비었다면 -1입니다.

불변 조건: 스택의 높이는 아래에서 위로 엄격하게 증가하며, 각 항목 바로 아래의 인덱스는 그 항목보다 낮은 가장 가까운 왼쪽 막대입니다. 두 막대 사이의 모든 막대는 그 항목 자체에 의해 또는 나중에 그 항목이 팝한 막대에 의해 지나가는 동안 팝되었으므로, 그중 해당 항목보다 낮은 막대는 없습니다. 끝내 팝되지 않는 막대는 맨 끝까지 이어지므로, 마지막 막대를 처리한 뒤 높이가 0인 막대를 하나 더 처리합니다. 이 막대는 모든 막대보다 낮으므로 스택을 비웁니다.

[2, 5, 6, 3, 4, 1]을 따라가 봅시다. 2, 5, 6을 푸시하면 스택에는 인덱스 [0, 1, 2]가 들어 있습니다. 인덱스 3의 3은 6을 팝하고(넓이 6 × (3-1-1) = 6), 이어서 5를 팝한 다음(넓이 5 × (3-0-1) = 10), 2에서 멈추고 푸시됩니다. 4를 푸시합니다. 인덱스 5의 1은 4를 팝하고(넓이 4), 이어서 3을 팝합니다. 이 직사각형은 인덱스 1부터 4까지 이어집니다. 3 × (5-0-1) = 12입니다. 2도 팝합니다(2 × 5 = 10. 스택이 비었으므로 너비는 5입니다). 끝맺는 0은 1을 팝합니다(1 × 6 = 6). 최댓값은 12입니다.

>=일 때 팝하면 높이가 같은 막대가 다른 막대를 일찍 멈추게 할 수 있습니다. 이는 안전합니다. 높이가 같은 막대가 스택에서 그 자리를 차지하고 같은 왼쪽 경계를 이어받으며, 나중에 팝될 때 전체 구간을 덮는 직사각형을 만듭니다. [3, 3, 3, 3]에서는 처음 세 개의 3이 너비 1, 2, 3을 기록하고, 마지막 3은 끝맺는 0에 의해 팝되면서 너비 4를 얻으므로, 넓이는 12입니다.