[Leet Code] Number of Subarrays with Bounded Maximum

こんにちは!今日、6月の3週目に3番目のアルゴリズムNumber of Subarrays with Bounded Maximumプールを作成します.

質問する

サマリ
与えられたnums配列において、部分配列のmax値がleft <= max <= rightである部分配列の個数を求めて戻される.

初志

二重forゲートの巡回では,部分配列を求める方法を思いついた.numsアレイにおいて、入力された値がleft <= nums[i] <= rightである場合、部分的なアレイが得られる.
しかし,有効部分配列の条件はmax値であることを無視した.
部分配列の第1の要素が必ずしもleftとrightの間の値ではないとしても、maxの値はleftとrightの間の値にすぎない.

第二の考え方

依然として2重forゲートを使用します.nums配列の値がrightより大きい場合にのみ、continueが処理されます.
1番目に入力された要素がleftとrightの間にある場合、resultを1に加算することができる.
次に、2番目のfor文を巡回して、部分配列を求めます.
結果は受け入れる!
次はコードの説明です.

コードの説明

int result = 0;

結果を返すresult変数を0に初期化します.

for (int i = 0; i < nums.length; i++) {
    if (nums[i] > right) continue;
    else if (nums[i] <= right && nums[i] >= left) result++;

	// ...
}

前門を巡回します.nums[i]がrightより大きい場合、部分配列は作成できないため、continueを処理する必要がある.nums[i]がleftとrightの間の値であれば、それ自体も部分的に配列されているので、result1を加えます.

for (int i = 0; i < nums.length; i++) {
    // ...
    
    int max = nums[i];

    // ...
}

その後、maxをnums[i]に設定し、2番目のfor文を巡回する.

for (int i = 0; i < nums.length; i++) {
    // ...
    
    for (int j = i + 1; j < nums.length; j++) {
        if (nums[j] > right) break;
        if (max < nums[j]) max = nums[j];

        if (max <= right && max >= left) result++;
    }
}

2番目のfor文は、iの次のインデックスから順次チェックされます.nums[j]がrightより大きい場合、breakを設定してfor文を終了します.これ以降は部分的な配列が成立しないためです.nums[j]がrightを超えない場合は、maxを変更します.
現在のmaxがmaxとleftの間にある場合、rightは加算される.
これは、resultがmax未満であるためである.

完全なコード

class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        int result = 0;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > right) continue;
            else if (nums[i] <= right && nums[i] >= left) result++;

            int max = nums[i];

            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] > right) break;
                if (max < nums[j]) max = nums[j];

                if (max <= right && max >= left) result++;
            }
        }

        return result;
    }
}

の最後の部分

今日も.私は問題を理解しないで盲目的にアルゴリズムを解くことに気づいた.
この欠点は直す必要があるが、性格がせっかちなのは問題ではないか、直せない.うううううう
とにかく.今回の位置付けを読んでいただき、ありがとうございました:)