LeetCoding Challenge Oct. 23: 132 Pattern

LeetCode October Challenge の 23 日目。

今日の問題は 132 Pattern。

問題の概要

• 与えられた配列 nums より、以下の条件を満たす長さ 3 のサブシーケンスが存在するかどうかを判定する
• 条件:
  • i < j < k
  • nums[i] < nums[k] < nums[j]
    • nums[i] < nums[j] < nums[k] ではない点に注意

考え方

• これは苦手なタイプの問題だ… 😭
• 問題文を見る限り、O(n * log(n)) や O(n) の解があるそうだか、ちょっと見当がつかないぞ…
• とりあえず、O(n^2) の解を考えよう
  • i を固定し、i + 1 以降の数値を対象に、nums[k] < nums[j] となるような数値を探し出す
    • i + 1 以降に現れた最大の数値を記録しておきつつ、それよりも小さい数値が現れたら 132 pattern が存在することになるわけですね
• このナイーブなアルゴリズムで実装 → submit → accept 👍
  • Runtime は 90ms で Your runtime beats 31.29 % of java submissions. 😭😭😭
• O(n * log(n)) は PriorityQueue とか TreeMap (TreeSet) とか使えばなんか実現できそうな気がするが、これというのは思いつかない…
• O(n) に至っては数時間考えてもまったく閃かず 🤦‍♂️

コード

class Solution {
    public boolean find132pattern(int[] nums) {
        if (nums.length < 3) {
            return false;
        }

        for (int i = 0; i < nums.length; i++) {
            int first = nums[i];
            int max = Integer.MIN_VALUE;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] <= first) {
                    continue;
                }

                if (nums[j] < max) {
                    return true;
                }
                max = nums[j];
            }
        }

        return false;
    }
}