단조 스택 계산기

스택 안의 값이 항상 오름차순이거나 내림차순이 되도록 유지하는 스택입니다. 새 값을 넣기 전에 그 값에 밀리는 것을 전부 꺼내면 남은 것은 모두 새 값보다 크므로, 얹어도 순서가 깨지지 않습니다. 「다음 큰 원소」처럼 각 원소의 좌우에서 처음 만나는 더 큰(또는 더 작은) 값을 찾는 문제를 O(n)에 풀 때 씁니다.

원소 하나가 스택에 들어가는 것도 한 번, 나오는 것도 한 번뿐이기 때문입니다. 안쪽 while이 몇 바퀴를 돌든 그 바퀴 수의 총합은 pop 횟수와 같고 pop은 push를 넘을 수 없으므로, 전체 연산이 2n번 이하입니다. 한 번의 while이 오래 도는 것은 그 앞에서 그만큼 조용히 지나간 값이 있었다는 뜻입니다.

「더 큰(>)」으로 볼지 「크거나 같은(≥)」으로 볼지에 따라 답이 달라집니다. [3, 3, 3]에서 >로 보면 세 원소 모두 답이 없고, ≥로 보면 앞의 둘은 바로 다음 칸이 답입니다. 이 도구는 둘을 모두 지원하니 문제에서 요구하는 쪽을 골라 쓰면 됩니다.

같은 값이 섞이면 얻을 수 없습니다. 다음 큰 원소를 >로 구하려면 자기보다 작은 것만 꺼내야 하는데, 그러면 남은 꼭대기는 「크거나 같은」 것이지 「큰」 것이 아닙니다. 부등호를 한쪽에 맞추면 반대쪽이 어긋나므로 부등호를 뒤집은 스택으로 한 번 더 훑습니다. 두 번 훑어도 여전히 O(n)입니다.

막대 i를 높이로 삼는 가장 넓은 직사각형이 좌우로 i보다 낮은 막대를 만나기 직전까지 뻗기 때문입니다. 곧 「이전 더 작은 원소」와 「다음 더 작은 원소」를 찾는 문제라, 부등호만 뒤집은 같은 코드로 풀립니다. 막대마다 후보가 하나씩 나오고 그중 가장 넓은 것이 답입니다.

반복이 끝난 뒤 스택에 남은 막대를 따로 처리하지 않기 위해서입니다. 오른쪽 끝에 높이 −1짜리 가상 막대를 하나 세우면 남아 있던 것이 전부 밀려나 예외 처리가 사라집니다. 이 보초를 빼먹고 마지막에 따로 처리하려다 폭 계산을 틀리는 것이 이 문제에서 가장 흔한 실수입니다.

주가의 「며칠 만에 신고가를 넘었는가」, 온도의 「며칠 뒤에 더 따뜻해지는가」 같은 문제가 그대로 다음 큰 원소입니다. 히스토그램 최대 직사각형은 이진 행렬에서 가장 큰 직사각형을 찾는 문제의 부분 문제로도 쓰이고, 슬라이딩 윈도 최댓값(단조 덱)도 같은 발상의 변형입니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.