连续子数组

2762。连续子数组

难度：中等

主题：滑动窗口、数组、有序集、堆（优先级队列）、队列、单调队列、两个指针、有序映射、哈希表、动态规划、计数、数学、二叉搜索树、线段树、树、堆栈、二分搜索、单调堆栈、记忆、迭代器、贪心、深度优先搜索、递归

给你一个0索引整数数组nums。如果满足以下条件，则 nums 的子数组称为连续的：

• 设 i, i 1, ..., j 为子数组中的索引。然后，对于每对索引 i 1, i₂ 1] - nums[i₂]|

返回连续子数组的总数。

子数组是数组中连续的非空元素序列。

示例1：

• 输入： nums = [5,4,2,4]
• 输出： 8
• 说明：
  • 大小为 1 的连续子数组：[5]、[4]、[2]、[4]。
  • 大小为 2 的连续子数组：[5,4]、[4,2]、[2,4]。
  • 大小为 3 的连续子数组：[4,2,4]。
  • 没有尺寸为 4 的子数组。
  • 连续子数组总数 = 4 3 1 = 8。
  • 可以证明不再有连续的子数组。

示例2：

• 输入： nums = [1,2,3]
• 输出： 6
• 说明：
  • 大小为 1 的连续子数组：[1]、[2]、[3]。
  • 大小为 2 的连续子数组：[1,2], [2,3].
  • 大小为 3 的连续子数组：[1,2,3]。
  • 连续子数组总数 = 3 2 1 = 6。

约束：

• 1 5
• 1 9

提示：

1. 尝试使用滑动窗口技术。
2. 使用集合或映射来跟踪子数组的最大值和最小值。

解决方案：

我们可以使用滑动窗口技术来高效计算连续子数组的数量。我们将维护一个有效窗口，其中子数组中的最大值和最小值之差最多为 2。为了有效地跟踪当前窗口内的最大值和最小值，我们可以使用两个 deques （一个一个为最大值，一个为最小值）。

方法

1. 使用带有两个指针的滑动窗口技术：左和右。
2. 使用两个双端队列：
   • 用于按降序跟踪元素索引以获得最大值。
   • 用于按升序跟踪元素索引以获得最小值。
3. 对于每个索引权：
   • 更新双端队列以反映当前窗口。
   • 确保窗口保持有效（最大值和最小值之差 ≤ 2）。如果无效，则增加左指针以缩小窗口。
   • 计算以索引 right 结尾的有效子数组的数量（右 - 左 1）。
4. 返回子数组的总数。

让我们用 PHP 实现这个解决方案：2762。连续子数组

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function continuousSubarrays($nums) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$nums1 = [5, 4, 2, 4];
echo continuousSubarrays($nums1) . "\n"; // Output: 8

$nums2 = [1, 2, 3];
echo continuousSubarrays($nums2) . "\n"; // Output: 6
?>

解释：

1. 滑动窗口：
   
   仅当窗口无效（即最大值与最小值之差超过2）时，左指针才会向前移动。右指针通过遍历数组来扩展窗口。

2. 最大值和最小值的双端队列：

   • maxDeque 始终按降序保存元素索引，确保当前窗口中的最大值位于前面 (maxDeque[0])。
   • minDeque 始终按升序保存元素索引，确保当前窗口中的最小值位于前面 (minDeque[0])。

3. 计算子数组：
   
   对于每个右侧，以右侧结尾的有效子数组的数量等于（右 - 左 1），因为从左到右的所有子数组都是有效的。

4. 效率：
   
   每个元素最多添加到双端队列中或从双端队列中删除一次，使得时间复杂度 O(n)。由于双端队列，空间复杂度为 O(n)。

输出

8
6

复杂性分析

1. 时间复杂度：

   • 每个元素最多从双端队列中推送和弹出一次。
   • 总时间复杂度为O(n)。

2. 空间复杂度：

   • 双端队列存储索引，最大大小为n。
   • 空间复杂度为O(n)。

此实现非常高效，并且在提供的约束范围内工作。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是连续子数组的详细内容。更多信息请关注PHP中文网其他相关文章！