모노톤 스택 Monotone Stack (JAVA)

📍 모노톤 스택이란?

: 스택 변형된 형태이다.
모노톤은 단조(monotonic)에서 유래된 말로,
스택 내에 저장된 데이터들이 단조 증가 또는 단조 감소하는 성질을 가지도록 유지하는 자료 구조이다.

1. 모노톤 스택 종류

• Monotonic Increasing Stack 모노톤 증가 스택
  : 스택에 들어오는 각 데이터가 커지거나 같은 스택이다.
  스택 top 쪽으로 갈수록 데이터가 큰 값이거나 같은 값이어야 한다는 것을 의미한다.

• Monotonic Decreasing Stack 모노톤 감소 스택
  : 스택에 들어오는 각 데이터가 작아지거나 같은 스택이다.
  스택 top 쪽으로 갈수록 값이 감소하거나 같은 값이어야 한다는 것을 의미한다.

2. 동작 방식

데이터를 스택에 삽입(추가)하기 전에 필요하지 않는 데이터를 먼저 스택에서 제거한 후 스택에 데이터를 삽입한다.

3. 문제

• 큰/작은 요소 찾기(Next Greater/Smaller Element) : 배열에서 각 데이터에 대해 오른쪽에 있는 첫 번째 더 큰(또는 더 작은) 데이터를 찾는 문제를 해결할 때 모노톤 스택을 사용한다.

4. 시간 복잡도

O(n)

5. 구현 JAVA

• 모노톤 증가 스택

Stack<Integer> stack = new Stack<>();  
     
for (int i = 0; i < 100; i++) {
	// 스택이 비어 있지 않고, 현재 데이터가 스택의 top 데이터보다 크면
    while (!stack.isEmpty() && stack.peek() > a) {
		stack.pop();
	}
	// 데이터를 스택에 삽입
	stack.push(a);
}

• 모노톤 감소 스택

Stack<Integer> stack = new Stack<>();  
     
for (int i = 0; i < 100; i++) {
	// 스택이 비어 있지 않고, 현재 데이터가 스택의 top 데이터보다 작으면
    while (!stack.isEmpty() && stack.peek() < a) {
		stack.pop(); 
	}
	// 데이터를 스택에 삽입
	stack.push(a);
}

6. 활용 JAVA

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

모노톤 감소 스택

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        Stack<Integer[]> stack = new Stack<>();
        for (int i = 0; i < N; i++) {
            int a = Integer.parseInt(st.nextToken());
            while (!stack.isEmpty()) {
                if (stack.peek()[0]>a) {
                    System.out.print(stack.peek()[1] + " ");
                    break;
                }
                stack.pop();
            }
            if (stack.isEmpty()) {
                System.out.print(0+" ");
            }
            stack.push(new Integer[]{a, i + 1});
        }
    }
}