LeetCode挑戦日記：Day8

はじめに

最近、業務で実装する時間よりも資料作成やレビューをする時間が多くなってきました。
このままでは自身のコーディング能力が落ちそうで怖いので、LeetCodeを始めてみました。

自身の学習の記録 & LeetCodeに興味のある人が挑戦しやすいように、記事に残していきます。
このような競技プログラミングをした経験がないので、ひよってEasyからやっていきます...

[Medium] 334. Increasing Triplet Subsequence

整数の配列numsが与えられたとき、i < j < k かつ nums[i] < nums[j] < nums[k]となるインデックスの三つ組 (i, j, k) が存在する場合はtrueを返し、存在しない場合はfalseを返す。

素直に解いてみる → NG

考え方

1. 配列を前からなめていき、条件を満たす組み合わせがあればtrueを返す

コーディング

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

結果

Time Limit Exceeded

改善：ループを減らす → NG

考え方

1. kのループをなくすために、事前に双子（右に大きい数字がある）かを確認しておく

コーディング

function increasingTriplet(nums: number[]): boolean {
    if (nums.length < 3) { return false; }

    const increasingTwin = new Array(nums.length).fill(true);
    let biggestNumber = nums[nums.length - 1];
    for (let i = nums.length - 2; 0 < i; i--) {
        if (biggestNumber <= nums[i]) {
            increasingTwin[i] = false;
            biggestNumber = nums[i];
        }
    }

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

    return false;
};

結果

Time Limit Exceeded

改善：更にループを減らす → OK

考え方

1. iのループを減らすために、三つ子か確認した末っ子の最小数を保持する

コーディング

function increasingTriplet(nums: number[]): boolean {
    if (nums.length < 3) { return false; }

    const increasingTwin = new Array(nums.length).fill(true);
    let biggestNumber = nums[nums.length - 1];
    for (let i = nums.length - 2; 0 < i; i--) {
        if (biggestNumber <= nums[i]) {
            increasingTwin[i] = false;
            biggestNumber = nums[i];
        }
    }

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

    return false;
};

結果

Runtime：158ms
Beats 5.75% of users with TypeScript

Memory：69.50MB
Beats 84.52% of users with TypeScript

他の人の解法

コーディング

function increasingTriplet(nums: number[]): boolean {
    let first = Infinity;
    let second = Infinity;

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] <= first) {
            first = nums[i];
        } else if (nums[i] <= second) {
            second = nums[i];
        } else {
            return true;
        }
    }
    return false;
};

結果

Runtime：61ms
Beats 99.21% of users with TypeScript

Memory：70.58MB
Beats 66.27% of users with TypeScript