[Array/String][Medium] 334. Increasing Triplet Subsequence

https://leetcode.com/problems/increasing-triplet-subsequence

Increasing Triplet Subsequence - LeetCode

 

Q. 증가하는 3개의 index와 그 값이 오름차순인 배열 조합이 있는지 여부를 반환하라.

    TC O(N), SC O(1)에 풀어라.

 

Comment.

 직관적으로 for문을 3번 돌면서 해당 조건을 만족하는지 찾으면 간단하다. 

 하지만, O(N)의 TC에 하기 위해서는 다른 접근이 필요하다.

 

 해당 조건을 만족하는 3개의 값을 찾는 동안, index는 증가하는 방향으로만 계산하면 된다. 

 간단하게, 해당 조건의 수가 만약 1개라면, 그 경우가 있는지 찾아보자. - 비교 대상이 없으므로, 어떤 배열이든 길이가 1이상이면 무조건 true일 것이다. 

 

 그렇다면 2개는? -  이전 값보다 큰 어떤 값을 만나면 무조건 true일 것이다. 그렇다면 이전 값보다 현재 index 값이 더 작다면? 두 값중 어떤 값이 필요할까?

 [2, 1, 2, X......]

 우리가 지금 index 1에 있다면, 이전값은 2이고, 현재 값은 1이다. 문제 조건 상, 다음 조건을 찾기 위해서 우리가 기억해야 할 값은 현재까지의 최소 값이어야 함을 알 수 있다. 따라서 지금까지의 최소값 즉, 1을 기억하게 하고, 다음 index에서 2를 만나, 최종적으로 해당 조건을 만족함을 알 수 있다.

 

 그렇다면 3개는? 이것은 2개의 연장이다. 2개인 경우를 만족하는 값을 찾고 저장했는데, 지금 값이 이전 이 2개의 값들보다 크면, 문제의 조건을 만족하게 되는 것이다. 

 이후 확장도 마찬가지. 

 

bool increasingTriplet(vector<int>& nums)
    {
        // 세개의 증가하는 배열 구간에 대해 해당 값이 역시 오름차순이 되는 구간이 있는지 여부를 반환하라.
        // -> TC O(N), SC O(1)에 풀수 있겠는가?
        // 
        int left = INT_MAX;
        int mid = INT_MAX;
        for (int k = 0; k < nums.size(); ++k)
        {
            if (nums[k] <= left)
                left = nums[k];
            else if (nums[k] <= mid)
                mid = nums[k];
            else return true;
        }
        return false;
    }