LeetCode 334. Increasing Triplet Subsequence

この記事はLeetCode337の解答を参考にしています。
元の問題：https://leetcode.com/problems/increasing-triplet-subsequence/
元の解答：https://leetcode.com/problems/increasing-triplet-subsequence/discuss/79004/Concise-Java-solution-with-comments.

問題

数字の配列が与えられる。i < j < kかつnums[i] < nums[j] < nums[k]となる組みが存在する場合はtrue、そうでない場合はfalseを返してください。

遅い解答

三重ループ。

for (let i = 0; i < nums.length - 2; i++) {
	for (let j = i + 1; j < nums.length - 1; j++) {
		for (let k = j + 1; k < nums.length; k++) {
			if (nums[i] < nums[j] && nums[j] < nums[k]) return true;
		}
	}
}
return false

一度の走査で見つける方法

まずi < j かつnums[i] < nums[j]の場合を考えてみる。走査をしていて

• これまで見た中で今の値より小さい値があるか

を考える。この値のベストケースはこれまで見た値の最小値のはずなので最小値だけを保存しておいて調べれば良い。

let c = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < nums.length; i++) {
	if (c > nums[i]) c = nums[i];
	if (c < nums[i]) return true;
}

同じ発想でこれまで見た中の１番目の最小値と２番目の最小値を保存しておく。

   public boolean increasingTriplet(int[] nums) {
        // start with two largest values, as soon as we find a number bigger than both, while both have been updated, return true.
        int small = Integer.MAX_VALUE, big = Integer.MAX_VALUE;
        for (int n : nums) {
            if (n <= small) { small = n; } // update small if n is smaller than both
            else if (n <= big) { big = n; } // update big only if greater than small but smaller than big
            else return true; // return if you find a number bigger than both
        }
        return false;
    }