[자료구조][스택] - 모노톤(단조) 스택

모노톤 스택이란?

스택에 데이터를 삽입할 때

데이터가 단조 증가 / 감소하는 스택

 

 

모노톤 스택 예시 (Java)

    public int[] nextGreaterElement(int[] nums) {
    
        int[] result = new int[nums.length]; // 결과 저장 배열
        Stack<Integer> stack = new Stack<>(); // 스택 선언

        for (int i = nums.length - 1; i >= 0; i--) { // 역순으로 순회
            while (!stack.isEmpty() && stack.peek() <= nums[i]) {
                stack.pop(); // 현재 값보다 작거나 같은 값은 스택에서 제거
            }
            result[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(nums[i]);
        }

        return result;
    }


    public static void main(String[] args) {
        int[] result = nextGreaterElement(new int[] {2, 1, 2, 4, 3});
        
        for (int r : result) {
            System.out.print(r + " "); // [4, 2, 4, -1, -1]
        }
    }