class Solution {
    
    // T: O(n^3)
    public boolean find132pattern(int[] nums) {
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] < nums[k] && nums[k] < nums[j])
                        return true;
                }
            }
        }
        
        return false;
    }
}

class Solution {
    
    // 132 패턴이 있으면 true를 반환
    // i < j < k and nums[i] < nums[k] < nums[j] 
    // T: O(n)
    public boolean find132pattern(int[] nums) {
        Stack<Integer> stack = new Stack<>(); // mono decreasing
        
        int second = Integer.MIN_VALUE;
        for (int i = nums.length - 1; i >= 0; i--) {
            // 앞의 숫자보다 작으면
            if (nums[i] < second) return true;
            // 
            while (!stack.isEmpty() && nums[i] > stack.peek()) {
                second = stack.pop();
            }
            stack.push(nums[i]);
        }
        
        return false;
    }
}