[leetcode] 334. Increasing Triplet Subsequence 문제 해결 보고서

1286 단어 LeetCode동적 기획
제목 링크:https://leetcode.com/problems/increasing-triplet-subsequence/
Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.
Formally the function should:
Return true if there exists 
i, j, k 
such that 
arr[i] < 
arr[j] < 
arr[k] given 0 ≤ 
i < 
j < 
k ≤ 
n-1 else return false.
Your algorithm should run in O(n) time complexity and O(1) space complexity.
Examples: Given  [1, 2, 3, 4, 5] , return  true .
Given  [5, 4, 3, 2, 1] , return  false .
사고방식: 본 문제는 가장 긴 승차순 서열의 방법으로 할 수 있지만 약간의 작은 문제를 크게 풀었다.현재 길이가 2인 승차순 서열(작은 값은small, 큰 값은big)을 유지할 수 있으며, 두 번째 값보다 큰 설명에 부딪히면 승차순의 세 가지 값을 찾을 수 있습니다.또한 이 과정에서 스몰과 빅의 값을 끊임없이 업데이트하여 그들을 최소화시켰다.
코드는 다음과 같습니다.
class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int small = INT_MAX, big = INT_MAX;
        for(auto val: nums)
        {
            if(val <= small) small = val;
            else if(val <= big) big = val;
            else return true;
        }
        return false;
    }
};
참조:https://leetcode.com/discuss/86891/concise-java-solution-with-comments

좋은 웹페이지 즐겨찾기