leetcodeノート: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.
二.テーマ分析
問題は,無秩序配列を与え,長さ3のインクリメンタルサブシーケンスが存在するか否かを判断することである.
すなわち、i, j, k(0 ≤ i < j < k ≤ n-1)が存在する場合、arr[i] < arr[j] < arr[k]はtrue、そうでなければfalseとなる.O(n)の時間的複雑さとO(1)の空間的複雑さを満たすことが要求される.
問題は、配列の中で3つの増加した要素を見つければよいことを要求し、この3つの要素が連続しているかどうかを要求しないので、2つの整数変数a, bを維持して、配列の中で大きさが増加した前の2要素を記録し、条件を満たす場合、a < b < nums[i]があるべきであることに注意しなければならない.
三.サンプルコード

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int n = nums.size();
        if (n < 3) return false;
        int a = INT_MAX, b = INT_MAX;
        for (int i = 0; i < n; ++i)
        {
            if (nums[i] <= a) a = nums[i];
            else if (nums[i] <= b) b = nums[i];
            else return true;
        }
        return false;
    }
};

四.小結
検索中は、aとbをできるだけ小さくするとともに、aがbより小さいことを保証する必要があります.