leetcode 2760 解决最长交替子数组问题_交替子数组和

# 解决最长交替子数组问题

**题目**:

```

给你一个下标从 0 开始的整数数组 nums 和一个整数 threshold 。

请你从 nums 的子数组中找出以下标 l 开头、下标 r 结尾 (0 <= l <= r < nums.length) 且满足以下条件的 最长子数组 ：

nums[l] % 2 == 0

对于范围 [l, r - 1] 内的所有下标 i ，nums[i] % 2 != nums[i + 1] % 2

对于范围 [l, r] 内的所有下标 i ，nums[i] <= threshold

以整数形式返回满足题目要求的最长子数组的长度。

注意：子数组 是数组中的一个连续非空元素序列

```

<br/>

在这个讨论中，我们探索了在一个整数数组中找到符合特定条件的最长交替子数组的不同方法。目标是找到一个以偶数开始，且其中相邻元素奇偶性交替，所有元素都不超过给定阈值的子数组。

## 方法探索

### 1. 直接遍历

- **思路**：通过直接遍历数组，检查每个可能的起始点，构建符合条件的子数组，并记录其长度。

- **实现细节**：使用两层循环，外层循环遍历所有元素作为可能的起始点，内层循环从这个点开始尝试构建子数组。

- **时间复杂度**：O(N^2)，由于内外两层循环。

- **代码**:

  ```csharp

  public class Solution {

      public int LongestAlternatingSubarray(int[] nums, int threshold) {

              int max = 0;

              for (int i = 0; i<nums.Length; i++)

              {

                  if (nums[i]%2 == 0)

                  {

                      if (nums[i]>threshold)

                      {

                          continue;

                      }

                      int l = i;

                      int r = i;

                      for (int j = i; j<nums.Length ; j++)

                      {

                              if (nums[j]>threshold)

                              {

                                  r = j-1;

                                  break;

                              }

                               if(j==nums.Length-1)

                                  {

                                      r=j;

                                      break;

                                  }

                          if ( nums[j] % 2 == nums[j + 1] % 2)

                          {

                              r =j;

                              break;

                          }

                       

                      }

                  int ans = r -l + 1;

                  if (ans > max)

                      {

                          max = ans;

                       

                          }

                     

                  }

              }

                  return max;

      }

  }

  ```

**      简洁版**:

```csharp

 public class Solution {

    public int LongestAlternatingSubarray(int[] nums, int threshold) {

        int max = 0;

        for (int i = 0; i < nums.Length; i++) {

            // 子数组必须以偶数开始

            if (nums[i] % 2 == 0 && nums[i] <= threshold) {

                int l = i;

                int r = i;

                while (r + 1 < nums.Length && nums[r + 1] <= threshold && nums[r] % 2 != nums[r + 1] % 2) {

                    r++;

                }

                // 更新最大子数组长度

                max = Math.Max(max, r - l + 1);

            }

        }

        return max;

    }

}

```

### 2. 动态规划

- **思路**：利用动态规划的思想，用一个变量记录到当前位置为止的最长符合条件的子数组长度。

- **实现细节**：逆向遍历数组，使用一个动态规划变量 `dp` 来跟踪到目前为止的最长有效子数组长度。

- **时间复杂度**：O(N)，因为只需要一次遍历。

- **代码**:

  ```csharp

  public class Solution {

      public int LongestAlternatingSubarray(int[] nums, int threshold) {

          int res = 0, dp = 0;

          for (int l = nums.Length - 1; l >= 0; l--) {

              if (nums[l] > threshold) {

                  dp = 0;

              } else if (l == nums.Length - 1 || nums[l] % 2 != nums[l + 1] % 2) {

                  dp++;

              } else {

                  dp = 1;

              }

              if (nums[l] % 2 == 0) {

                  res = Math.Max(res, dp);

              }

          }

          return res;

      }

  }

  ```

### 3. 状态机方法

- **思路**：使用状态机来管理数组遍历过程中的不同阶段，例如寻找起始点、构建子数组等。

- **实现细节**：定义多个状态，如“寻找起始偶数”、“构建交替子数组”，根据当前元素和条件来转换状态。

- **时间复杂度**：O(N)，每个元素只需要处理一次。

- **代码**:

  ```csharp

  public class Solution {

      public int LongestAlternatingSubarray(int[] nums, int threshold) {

          int maxLength = 0;

          int currentLength = 0;

          State currentState = State.Searching;

          foreach (var num in nums) {

              switch (currentState) {

                  case State.Searching:

                      if (num % 2 == 0 && num <= threshold) {

                          currentState = State.Building;

                          currentLength = 1;

                      }

                      break;

                  case State.Building:

                      if (num > threshold || num % 2 == nums[currentLength - 1] % 2) {

                          currentState = State.Searching;

                          maxLength = Math.Max(maxLength, currentLength);

                          currentLength = 0;

                      } else {

                          currentLength++;

                      }

                      break;

                  case State.Invalid:

                      currentState = num % 2 == 0 && num <= threshold ? State.Building : State.Searching;

                      break;

              }

          }

          if (currentState == State.Building) {

              maxLength = Math.Max(maxLength, currentLength);

          }

          return maxLength;

      }

      enum State {

          Searching,

          Building,

          Invalid

      }

  }

  ```

### 4. 前缀和技术

- **思路**：尽管这个问题不是典型的前缀和问题，但可以尝试使用前缀和的概念来追踪到当前位置的最长交替子数组长度。

- **实现细节**：构建一个前缀数组，其中每个元素代表到该点的最长符合条件的子数组长度。

- **时间复杂度**：O(N)，由于单次遍历。

- **代码**:

  ```csharp

  public class Solution {

      public int LongestAlternatingSubarray(int[] nums, int threshold) {

          int n = nums.Length;

          int[] prefix = new int[n];

          int maxLen = 0;

          for (int i = 0; i < n; i++) {

              if (i == 0) {

                  prefix[i] = (nums[i] % 2 == 0 && nums[i] <= threshold) ? 1 : 0;

              } else {

                  if (nums[i] <= threshold && nums[i] % 2 != nums[i - 1] % 2) {

                      prefix[i] = prefix[i - 1] + 1;

                  } else {

                      prefix[i] = (nums[i] % 2 == 0 && nums[i] <= threshold) ? 1 : 0;

                  }

              }

              if (nums[i] % 2 == 0) {

                  maxLen = Math.Max(maxLen, prefix[i]);

              }

          }

          return maxLen;

      }

  }

  ```

### 5. 辅助数组

- **思路**：与动态规划类似，使用一个辅助数组来记录到每个位置为止的最长交替子数组长度。

- **实现细节**：在遍历数组时更新辅助数组，根据当前元素和前一个元素的奇偶性以及阈值条件来更新。

- **时间复杂度**：O(N)，单次遍历实现。

- **代码**:

  ```csharp

  public class Solution {

      public int LongestAlternatingSubarray(int[] nums, int threshold) {

          if (nums.Length == 0) return 0;

          int[] maxLengths = new int[nums.Length];

          int res = 0;

          for (int i = 0; i < nums.Length; i++) {

              if (nums[i] > threshold) {

                  maxLengths[i] = 0;

              } else if (i == 0) {

                  maxLengths[i] = nums[i] % 2 == 0 ? 1 : 0;

              } else if (nums[i] % 2 != nums[i - 1] % 2) {

                  maxLengths[i] = nums[i - 1] <= threshold ? maxLengths[i - 1] + 1 : 1;

              } else {

                  maxLengths[i] = 1;

              }

              if (nums[i] % 2 == 0) {

                  res = Math.Max(res, maxLengths[i]);

              }

          }

          return res;

      }

  }

  ```

<br/>

### 6. 滑动窗口

- **思路**：使用滑动窗口来动态地调整子数组的大小，寻找最长的符合条件的子数组。

- **实现细节**：维护一个窗口，该窗口从满足条件的起始偶数开始，直到遇到不符合条件的元素或数组结束。窗口的大小随着遍历动态变化。

- **代码**:

  ```csharp

  public class Solution {

      public int LongestAlternatingSubarray(int[] nums, int threshold) {

          int maxLength = 0;

          int start = -1;

          for (int i = 0; i < nums.Length; i++) {

              // 如果当前元素超过阈值或者与前一个元素奇偶性相同

              if (nums[i] > threshold || (i > 0 && nums[i] % 2 == nums[i - 1] % 2)) {

                  start = -1;  // 重置起始点

              }

              // 如果找到一个合适的起始点（偶数且不超过阈值）

              if (start == -1 && nums[i] % 2 == 0 && nums[i] <= threshold) {

                  start = i;

              }

              // 更新最长长度

              if (start != -1) {

                  maxLength = Math.Max(maxLength, i - start + 1);

              }

          }

          return maxLength;

      }

  }

  ```

<br/>

### ### 7. 分组

- **思路**：将数组划分为若干个符合条件的连续子数组（分组），然后找出这些分组中最长的一个。

- **实现细节**：遍历数组，当遇到不符合条件的元素时，结束当前分组并开始新的分组。分组的长度取决于其起始偶数和满足交替条件的连续元素序列。

- **时间复杂度**：O(N)，因为数组只被遍历一次。

- **代码**:

  ```csharp

  public class Solution {

      public int LongestAlternatingSubarray(int[] nums, int threshold) {

          int n = nums.Length;

          int ans = 0, i = 0;

          while (i < n) {

              if (nums[i] > threshold || nums[i] % 2 != 0) {

                  i++; // 直接跳过不符合条件的元素

                  continue;

              }

              int start = i; // 记录这一组的开始位置

              i++; // 从下一个位置开始判断

              while (i < n && nums[i] <= threshold && nums[i] % 2 != nums[i - 1] % 2) {

                  i++;

              }

              // 计算从 start 到 i-1 的子数组长度，并更新最长长度

              ans = Math.Max(ans, i - start);

          }

          return ans;

      }

  }

  ```

<br/>

## 核心发现和结论

- **核心发现**：尽管这些方法在实现上有所不同，但它们在逻辑上都涉及到了对数组进行“分组”的思路。每种方法都是在识别和处理数组中符合特定条件的连续部分，即分组。

- **结论**：在解决编程问题时，不同的方法往往可以归结为几个基本的思想。理解这些相似性有助于更深入地理解问题本身，并可以更灵活地应用不同的方法来解决类似的问题。在这个特定问题中，多种方法最终都回归到了相似的逻辑框架上，即“分组”。

这次讨论提供了对于解决特定数组处理问题的多角度视野，展示了即使在看似简单的问题上，也有多种不同的解决策略可供选择。