LeetCode 2020-11-16: Longest Mountain in Array

Longest Mountain in Array (medium) の挑戦メモ。

問題の概要

• 与えられた配列の部分配列のうち、山のようになっているものの最大の長さを求める
• ここでいう「山」とは、長さ n の部分配列 s の要素が s[0] < s[1] < ... < s[t - 1] < s[t] > s[t + 1] > ... > s[n - 2] > s[n - 1] という関係になっているものを指す
  • 隣り合う要素が等しい値になることはない

考え方

• これはステートマシンを使えば時間計算量 O(n) で解けそうですね
  • 「山に登っていない状態」「山登り中」「山下り中」の 3 つの状態を考える
  • s[i] < s[i + 1] という関係が見つかったら「山登り中」に遷移する
    • 「山下り中」に見つけたら、それまでの山の長さを求めておく
  • 「山登り中」に s[i] > s[i + 1] という関係が見つかったら「山下り中」に遷移する
  • s[i] == s[i + 1] という関係が見つかったら、「山に登っていない状態」に遷移する
• 実装して submit → accept 👍
  • Runtime 2ms で Your runtime beats 85.91 % of java submissions.
  • あと 1ms 早くできれば 100% beats になれるのだが…
• ステートマシンではない解法も実装して submit してみたが、1ms の壁は厚く破れなかった 😵

コード

ステートマシンによる解法

class Solution {
    public int longestMountain(int[] A) {
        if (A.length < 3) {
            return 0;
        }

        int state = 0;
        int begin = 0;
        int result = 0;
        int prev = A[0];

        for (int i = 1; i < A.length; i++) {
            int cur = A[i];
            switch (state) {
                case 0:  // 初期状態
                    if (prev < cur) {
                        state = 1;
                        begin = i - 1;
                    }
                    break;

                case 1:  // 山登り中
                    if (prev == cur) {
                        state = 0;
                    } else if (prev > cur) {
                        state = 2;
                    }
                    break;

                case 2:  // 山下り中
                    if (prev <= cur) {
                        result = Math.max(result, i - begin);
                        if (prev < cur) {
                            state = 1;
                            begin = i - 1;
                        } else {
                            state = 0;
                        }
                    }
                    break;
            }
            prev = cur;
        }

        if (state == 2) {
            return Math.max(result, A.length - begin);
        }

        return result;
    }
}

ステートマシンを使わない愚直な実装

class Solution {
    public int longestMountain(int[] A) {
        if (A.length < 3) {
            return 0;
        }

        int result = 0;

        for (int i = 1; i < A.length; ) {
            if (A[i - 1] >= A[i]) {
                i++;

            } else {
                int begin = i - 1;

                while (++i < A.length) {
                    if (A[i - 1] > A[i]) {
                        while (++i < A.length && A[i - 1] > A[i])
                            ;

                        result = Math.max(result, i - begin);
                        begin = i - 1;
                    }
                    if (i >= A.length || A[i - 1] == A[i]) {
                        break;
                    }
                }
            }
        }

        return result;
    }
}