問題概要

2012. 配列の美しさ値の合計

0から始まる整数配列 arr が与えられます。各インデックス i（1 <= i <= arr.length - 2）について、arr[i] の 美しさ値 は以下のように定義されます：

• 2、すべての 0 <= j < i かつ i < k <= arr.length - 1 について arr[j] < arr[i] < arr[k] が成立する場合
• 1、arr[i-1] < arr[i] < arr[i+1] が成立し、かつ最初の条件を満たさない場合
• 0、上記の条件のいずれも満たさない場合

1 <= i <= arr.length - 2 を満たすすべての arr[i] の 美しさ値の合計 を返してください。

例1：

入力：arr = [1,2,3]
出力：2
説明：範囲 1 <= i <= 1 を満たす各インデックス i について：
- arr[1] の美しさ値は 2

例2：

入力：arr = [2,4,6,4]
出力：1
説明：範囲 1 <= i <= 2 を満たす各インデックス i について：
- arr[1] の美しさ値は 1
- arr[2] の美しさ値は 0

例3：

入力：arr = [3,2,1]
出力：0
説明：範囲 1 <= i <= 1 を満たす各インデックス i について：
- arr[1] の美しさ値は 0

制約：

• 3 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^5

解法

まず問題を理解しましょう。範囲 1 <= i <= arr.length - 2 を満たすインデックス i について、美しさ値は3つのケースがあります：

• 美しさ値 = 2：i位置より前のすべての要素が arr[i] より小さく、i位置より後のすべての要素が arr[i] より大きい場合
• 美しさ値 = 1：最初の条件を満たさないが、直前の要素が arr[i] より小さく、直後の要素が arr[i] より大きい場合
• 美しさ値 = 0：上記2つの条件のいずれも満たさない場合

したがって、範囲内の各 i について美しさ値を判定する必要があります。ケース1を個別に比較する場合、単一の i を判定する時間計算量は O(n) となり、全体の時間計算量は O(n^2) になります。ケース2は前後の要素のみを比較するため、単一の i を判定する時間計算量は O(1) です。ケース3は上記2つのケースが判定された後、個別の判定は不要です。

したがって、主な最適化ポイントはケース1をどのように高速に判定するかです。2つの補助配列 prefixMax[] と suffixMin[] を構築します。prefixMax[i] はインデックス [0, i] 範囲内の最大値を、suffixMin[i] はインデックス [i, n-1] 範囲内の最小値を表します。これらの補助配列があれば、位置 i がケース1を満たすか判定する時間は、条件 prefixMax[i-1] < arr[i] && arr[i] < suffixMin[i+1] を判定するだけで済み、各判定の時間計算量は O(1) に削減されます。範囲内の i を判定する時間計算量は O(n) です。これらの補助配列を構築するには、元の配列をそれぞれ前から後ろへ、後ろから前へ走査する必要があり、時間計算量も O(n) です。これにより、O(n^2) の時間計算量を回避できます。

さらに、前から後ろに i を処理する場合、prefixMax[] 配列を作成する必要はなく、[0, i] 範囲内の最大値を表す prefixMax 変数をローリングで維持するだけで済みます。これにより、サイズ n の配列の空間オーバーヘッドを節約できます。同様に、後ろから前に i を処理する場合、suffixMin[] の空間を節約できます。ただし、両方を同時に節約することはできません。

コード実装

class Solution {
    public int calculateBeautySum(int[] arr) {
        int[] suffixMin = computeSuffixMinimums(arr);
        int result = 0;
        int prefixMax = arr[0];
        
        for (int i = 1; i < arr.length - 1; i++) {
            if (arr[i] > prefixMax && arr[i] < suffixMin[i + 1]) {
                result += 2;
            } else if (arr[i] > arr[i - 1] && arr[i] < arr[i + 1]) {
                result += 1;
            }
            // 次のiに進むときのarr[0, i-1]の最大値を計算
            prefixMax = Math.max(prefixMax, arr[i]);
        }
        return result;
    }

    /**
     * 後ろから前へ、現在のインデックスから配列の末尾までの最小値を求める
     */
    private int[] computeSuffixMinimums(int[] arr) {
        int n = arr.length;
        int[] suffixMin = new int[n];
        suffixMin[n - 1] = arr[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suffixMin[i] = Math.min(suffixMin[i + 1], arr[i]);
        }
        return suffixMin;
    }
}

アルゴリズムの複雑さ

• 時間計算量: O(n) - 配列を2回（前からと後ろから）走査するため
• 空間計算量: O(n) - suffixMin配列のため