🌟

LeetCoding Challenge Oct. 23: 132 Pattern

2020/10/24に公開約1,300字

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;
    }
}

Discussion

ログインするとコメントできます