monotone stack

monotone stack

monotone stack은 특정 index에서 주변을 탐색하며 개수를 구해줄 때 특정상황에서 O(n)으로의 시간복잡도로 줄여주는 알고리즘 입니

다.

 

사용 방법

stack의 원소들을 오름차순 or 내림차순 상태로 유지시키는 방법입니다. 

 

예시

1 3 10 50 20 16 19 49 30이 있다고 가정해봅시다. 오름차순으로 stack에 넣으려고 합니다.

 

1 3 10 50 까지는 오름차순이기 때문에 pop 과정이 없지만, 20을 넣는 순간 오름차순이 깨지기 때문에 pop과정이 발생합니다.

 

1 3 10 50 20이 되고 모든 데이터를 넣으면  3 10 50 20 16 19 49 30 으로 3 10 16 19 30만 남아 있는 상태가 됩니다.

 

 

사용 이유 

이렇게 스택의 원소를 정렬하면, 특정 index 보다 왼쪽에 있는 값 중에서 처음으로 나오는 특정 index 미만의 수의 값을 바로 알 수 있습니다.

 

 

관련한 문제

6198번: 옥상 정원 꾸미기

문제를 풀어보면 모든 위치에서 오른쪽으로 볼 수 있는 정원의 개수를 구하는 문제입니다. 문제의 설명대로 구현한다면 최악의 경우 O(n^2)의 시간복잡도로 풀어야 정확하게 풀 수 있습니다. 하지만, monotone stack을 사용한다면 O(n)의 시간복잡도로 풀어낼 수 있습니다. 고민해보며 풀어보고 생각이 나지 않는다면 아래의 풀이 방법을 이해해보세요.

 

 

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        InputReader in = new InputReader(System.in);

        int n = in.nextInt();
        Stack<Integer> s = new Stack<>();
        long answer = 0;
        for(int i = 0; i < n; i++) {
            int building = in.nextInt();

            while(!s.isEmpty()) {
                if(s.peek() > building) break;

                s.pop();
            }
            answer += s.size();
            s.push(building);
        }
        System.out.println(answer);
    }
}