모노톤 스택은 언제 떠올려야 할까: 다음 큰 수와 히스토그램 문제를 잇는 사고법

모노톤 스택는 이름만 보고 판단하면 핵심을 놓치기 쉬운 주제입니다. 이 글은 최신 출처와 구조를 기준으로 독자가 실제로 확인해야 할 기준을 정리합니다.

핵심은 모노톤 스택을 떠올리는 문제 패턴 이해입니다. 단정적인 결론보다 확인 순서와 리스크를 분리해 보는 것이 중요합니다.

모노톤 스택 흐름을 그림으로 보기

모노톤 스택은 스택을 정렬해 두는 것이 아니다

모노톤 스택은 스택 전체를 정렬 자료구조처럼 쓰는 개념이 아닙니다. 스택에 남아 있는 원소들이 증가 또는 감소 순서를 유지하도록 관리하면서, 답이 확정된 원소를 바로 제거하는 패턴입니다.

핵심은 스택에 아직 답을 찾지 못한 인덱스만 남기는 것입니다.

다음 큰 수 문제로 감각 잡기

배열에서 각 원소의 오른쪽에 있는 첫 번째 더 큰 값을 찾는다고 생각해보겠습니다. 완전탐색을 하면 각 위치마다 오른쪽을 다시 훑어야 해서 O(n²)이 됩니다.

모노톤 스택은 아직 더 큰 값을 만나지 못한 인덱스를 스택에 넣어둡니다. 현재 값이 스택 top보다 크면, 현재 값이 바로 그 top의 다음 큰 수가 됩니다.

vector nextGreater(vector& a) {
    int n = a.size();
    vector ans(n, -1);
    stack st;

    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) {
            ans[st.top()] = a[i];
            st.pop();
        }
        st.push(i);
    }
    return ans;
}

vector nextGreater(vector& a) {
    int n = a.size();
    vector ans(n, -1);
    stack st;

    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) {
            ans[st.top()] = a[i];
            st.pop();
        }
        st.push(i);
    }
    return ans;
}

왜 O(n)이 되는가

while문이 들어가면 겉으로는 느려 보입니다. 하지만 각 인덱스는 스택에 한 번 push되고, 조건이 맞을 때 한 번 pop됩니다. 같은 원소가 여러 번 pop될 수 없습니다.

그래서 전체 pop 횟수는 최대 n번이고, 전체 시간복잡도는 O(n)입니다. 이 설명을 이해하면 모노톤 스택 문제에서 while문을 두려워하지 않아도 됩니다.

히스토그램 문제와 연결하기

히스토그램 최대 직사각형 문제에서는 각 막대가 어디까지 확장될 수 있는지를 찾아야 합니다. 이때는 현재 막대보다 큰 막대들을 pop하면서, pop된 막대의 오른쪽 경계를 현재 위치로 확정합니다.

long long largestRectangle(vector& h) {
    int n = h.size();
    stack st;
    long long ans = 0;

    for (int i = 0; i <= n; i++) {
        int cur = (i == n ? 0 : h[i]);
        while (!st.empty() && h[st.top()] > cur) {
            int height = h[st.top()];
            st.pop();
            int left = st.empty() ? -1 : st.top();
            int width = i - left - 1;
            ans = max(ans, 1LL * height * width);
        }
        st.push(i);
    }
    return ans;
}

long long largestRectangle(vector& h) {
    int n = h.size();
    stack st;
    long long ans = 0;

    for (int i = 0; i <= n; i++) {
        int cur = (i == n ? 0 : h[i]);
        while (!st.empty() && h[st.top()] > cur) {
            int height = h[st.top()];
            st.pop();
            int left = st.empty() ? -1 : st.top();
            int width = i - left - 1;
            ans = max(ans, 1LL * height * width);
        }
        st.push(i);
    }
    return ans;
}

언제 떠올리면 좋을까

1. 오른쪽 또는 왼쪽의 첫 번째 큰 값/작은 값을 찾는다
2. 각 원소의 영향 범위가 어디까지인지 묻는다
3. 완전탐색으로는 같은 비교를 반복한다
4. 답이 확정되는 순간 원소를 제거할 수 있다
5. 스택에 남길 순서가 증가 또는 감소로 정해진다

정리

모노톤 스택은 외워야 할 특수 기술이 아니라, 답을 아직 모르는 원소를 순서 있게 보관하다가 답이 확정되면 제거하는 사고법입니다. 다음 큰 수, 주식 가격, 히스토그램 문제를 같은 패턴으로 묶어 보면 훨씬 덜 낯설어집니다.

관련 글로는 자바 HashMap은 어떻게 key를 찾을까, 투 포인터 알고리즘이란 무엇인가, 덱으로 푸는 슬라이딩 윈도우 최댓값을 함께 보면 좋습니다. 외부 기준은 AtCoder editorial – monotonic stack example, Codeforces monotonic stack tutorial, Baeldung – Monotonic Stack을 확인했습니다.