334. Increasing Triplet Subsequenc

⚡문제정보

i < j < k 가 성립해야하는데

꼭 순서대로 성립하지 않아도 괜찮습니다. 즉 좀 띄엄띄엄있어도

i < j < k이기만 하면 true를 반환하는 조건입니다.

예컨대 아래 배열같은 경우 true를 반환해야할것입니다.

[ 10 , 2 , 12 , 5 , 3 , 8 ]

---

🔍접근방법

그리디 알고리즘을 통해 O(n)으로 해결할 수 있을 것 같습니다.

예를 들어 가장 작은 값과 가장 작은 값보다 큰 값을 정해준뒤

nums[i]를 계속 업데이트해주면서 나아가는거죠!

---

🔍나의 풀이

var increasingTriplet = function(nums) {
    let Max1 = Infinity
    let Max2 = Infinity
    for(i=0 ; i< nums.length; i++) {
        if(Max1 < Max2 && Max2 < nums[i]) return true
        if( nums[i] < Max1) Max1 = nums[i]
        if( nums[i] > Max1 && nums[i] < Max2) Max2 = nums[i]
        
    }
    return false
};

간단한 알고리즘입니다.

만약 nums[i]가 Max1보다 크면 Max1에 nums[i]를 넣어줍니다.

nums[i]가 Max1보다는 크지만 Max2보다는 작으면 Max2값을 업데이트해줍니다.

그뒤 Max2보다 nums[i]가 크면 true를 뱉고

반복문의 끝에 도달할때까지 true를 반환하지 못하면 false를 반환하게합니다.