Leetcode - 334. Increasing Triplet Subsequence

문제

주어진 배열에서 아래 조건을 만족하는 세개의 값이 존재하면 true리턴

• i < j < k and nums[i] < nums[j] < nums[k]

Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

해결 아이디어

• LIS 문제의 풀이방법으로 해결 (https://velog.io/@soopsaram/Leetcode-300.-Longest-Increasing-Subsequence)
  • O(n^2)의 dp 방법으로 했을때는 TLE나왔음. 예제가 [1111...겁나많음...123] 인경우에.
  • sub배열 생성 알고리즘으로 해결했을때는 통과 (알고리즘 설명은 Leetcode-300 LIS 참고)
  • 풀이방식은 LIS와 동일하고, 길이가 3이상이면 true를 바로 리턴

풀이 O(n^2)

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        vector<int> sub;
        sub.push_back(nums[0]);
        for (int i = 1; i < nums.size(); i++) {
            if (sub[sub.size() - 1] < nums[i]) {
                sub.push_back(nums[i]);
            } else {
                int j = 0;
                while (sub[j] < nums[i]) j++;
                sub[j] = nums[i];
            }
            if (sub.size() >= 3)
                return true;
        }
        return false;
    }
};

풀이 O(nlogn)

위의 풀이방법에서 sub 배열에서 값을 찾는것을 이진탐색하면 된다. sub배열은 값이 정렬된 배열이기 때문에 이진탐색이 가능하다.

class Solution {
public:
    int binary_search(vector<int> &sub, int tgt) {
        int left = 0;
        int right = sub.size() - 1;
        int mid = 0;
        
        while (left < right) {
            mid = left + (right - left) / 2;
            if (sub[mid] == tgt) {
                return mid;
            } else if (sub[mid] < tgt) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
    bool increasingTriplet(vector<int>& nums) {
        vector<int> sub;
        sub.push_back(nums[0]);
        for (int i = 1; i < nums.size(); i++) {
            if (sub[sub.size() - 1] < nums[i]) {
                sub.push_back(nums[i]);
            } else {
                // find position in sub[] with binary search
                int pos = binary_search(sub, nums[i]);
                sub[pos] = nums[i];
            }
            if (sub.size() >= 3)
                return true;
        }
        return false;
    }
};

풀이 O(n)

우선 first, second변수를 최대값으로 초기화 하고, 배열을 순회하면서 이 변수를 가장 작은값, 그다음 작은값으로 업데이트 하는방식이다.

솔루션에서 배운 풀이방법인데, 대단히 간결하고 신박하다. 게다가 O(n) 시간복잡도를 갖는다. 같은 원리로 3개 뿐만아니라 고정된 k개의 increasing subsequence가 존재하는지 찾는 문제는 모두 이 방식으로 해결이 가능하다. 시간복잡도도 O(n).

[1,2,0,3] 의 경우

    2st 값이 없데이트 되었다는 의미는, 이전에 1st값이 반드시 존재했었다는것을 의미 (이전 시점의 1st 값보다는 반드시 크다)
    |     
    |     * <---- 3st도 마찬가지, 따라서 지금까지의 2st보다 큰 값이 있다는건, 결국 1st 2st 3st 이렇게 점진적으로 증가하는 sub sequence가 존재한다는것을 의미
    *   
 *    
       *
 1  2  0  3

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int first = INT_MAX;
        int second = INT_MAX;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] <= first) // 기존에 업데이트한 first값보다 작은경우 재 업데이트.
                first = nums[i];
            else if (nums[i] <= second) // 자동으로 first보다 크면서 second보다 작거나같은 값을 다시 업데이트
                second = nums[i];
            else                  // second보다 큰값이 존재한다는것은 3번의 증가하는 subsequence가 있다는 의미.
                return true;
        }
        return false;
    }
};

오답들

아래는 pass가 되기전까지 시도해봤던 아이디어인데, 왜 오류가 났을지 생각해보자.

• TLE

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        vector<int> sub;
        sub.push_back(nums[0]);
        for (int i = 1; i < nums.size(); i++) {
            if (sub[sub.size() - 1] < nums[i]) {
                sub.push_back(nums[i]);
            } else {
                int j = 0;
                while (sub[j] < nums[i]) j++;
                sub[j] = nums[i];
            }
            if (sub.size() >= 3)
                return true;
        }
        return false;
    }
};

• Monotonic Stack 방법

20 100 10 12 5 13 의 경우는 오답. 바로 직전 작은 값만 가리키기 때문.

/*
index  0 1 2 3 4 5    
nums   1 5 0 4 1 3

index         [2]  [4]  [5]
nums[i]        0 <- 1 <- 3
nr_link        3    2    1
*/
class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int last_idx = nums.size() - 1;
        stack<pair<int, int>> st; // contain <index, nums>
        vector<int> nr_link(nums.size(), 1);
        
        // increasing monotonic stack -> next small value
        st.push(make_pair(last_idx, nums[last_idx]));
        for (int i = last_idx - 1; i >= 0; i--) { // from the last to begin
            int max_nr_link = 0;
            int candidate_max = 0;
            while (!st.empty() && nums[i] < st.top().second) {
                pair<int, int> elem = st.top();
                st.pop();
                // find maximum number of linked 
                candidate_max = nr_link[i] + nr_link[elem.first]; 
                max_nr_link = std::max(candidate_max, max_nr_link);
            }
            nr_link[i] = max_nr_link;
            if (nr_link[i] >= 3)
                return true;
            st.push(make_pair(i, nums[i]));
        }
        return false;
    }
};