[LeetCode] 456. 132 Pattern

https://leetcode.com/problems/132-pattern/description/

LeetCode - The World's Leading Online Programming Learning Platform

문제 유형 : 스택 / 배열

문제 난이도 : Medium

 

문제

Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].

Return true if there is a 132 pattern in nums, otherwise, return false.

 

정수 배열 nums에서 132패턴을 찾아라.

132패턴은 인덱스 i < j < k에서 nums[i] < nums[k] < nums[j]의 형태를 말한다.

132패턴이 있으면 true를, 아니면 false를 반환하라.

 

접근 방법은 다음과 같습니다:

1. 감소하는 요소를 추적하기 위한 스택을 생성.
2. maxThird를 가능한 가장 작은 값으로 초기화.
3. 배열을 오른쪽에서 왼쪽으로 순회하며 각 요소에 대해 다음을 수행: b. 스택이 비어있지 않고 스택의 맨 위 요소가 현재 요소보다 작으면, maxThird를 스택의 맨 위 요소로 업데이트하고, 스택의 맨 위 요소를 꺼냄.
   1.  현재 요소를 스택에 삽입.
   2. 현재 요소가 maxThird보다 작으면 true를 반환하여 132 패턴을 찾았음을 나타냄.
4. 배열을 순회한 후에도 132 패턴을 찾지 못했다면 false를 반환.

 

코드

C++

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        const int n = nums.size();

        if (n < 3)
            return false;

        stack<int> s;

        int maxThird = INT_MIN;

        for (int i = n - 1; i >= 0; i--) {
            int curr = nums[i];

            if (curr < maxThird)
                return true;

            while (!s.empty() && s.top() < curr) {
                maxThird = s.top();
                s.pop();
            }

            s.push(curr);
        }

        return false;
    }
};