使用C++编写代码，找到具有相同最小值和最大值的子数组的数量
在算法设计与数据结构领域，子数组问题是一类经典且具有挑战性的题目。子数组通常指数组中连续的元素序列，其分析广泛应用于统计分析、信号处理、金融建模等领域。本文聚焦于一个特定问题：给定一个整数数组，如何高效计算其中所有满足最小值等于最大值的子数组数量。该问题不仅考验对数组遍历和边界条件的处理能力，更要求在时间复杂度与空间复杂度之间寻求最优解。
从问题本质来看，每个子数组的最小值和最大值是否相等，直接决定了其是否满足条件。若直接采用暴力枚举法，即遍历所有可能的子数组并逐一计算其极值，时间复杂度将高达O(n³)，这在处理大规模数据时显然不可行。因此，优化算法的核心在于如何避免重复计算极值，并利用数学规律减少不必要的遍历。
一、问题分析与数学建模
设输入数组为arr，长度为n。我们需要统计所有满足以下条件的子数组arr[i..j]的数量：
min(arr[i], arr[i+1], ..., arr[j]) == max(arr[i], arr[i+1], ..., arr[j])显然，只有当子数组中的所有元素相等时，其最小值与最大值才会相等。因此，问题可转化为：统计所有由相同元素组成的连续子数组的数量。
进一步分析可知，若数组中存在连续的k个相同元素，则这些元素可构成k*(k+1)/2个子数组（包括长度为1到k的所有可能）。例如，数组[2,2,2]中，长度为1的子数组有3个，长度为2的有2个，长度为3的有1个，总计6个。
二、算法设计与实现
基于上述分析，算法可分解为以下步骤：
- 遍历数组，识别连续的相同元素块
- 对每个块，计算其可构成的子数组数量
- 累加所有块的结果，得到最终答案
具体实现时，可通过双指针法标记连续相同元素的起始与结束位置。例如，初始化指针i=0，遍历数组，当arr[i] != arr[i+1]时，记录当前连续块的长度len = i - start + 1，并计算该块的子数组数量len*(len+1)/2。随后更新start指针，继续后续遍历。
1. 基础实现代码
#include
#include
using namespace std;
int countSubarraysWithEqualMinMax(const vector& arr) {
int n = arr.size();
if (n == 0) return 0;
int total = 0;
int start = 0; // 连续相同元素的起始索引
for (int i = 1; i 上述代码的时间复杂度为O(n)，空间复杂度为O(1)，已达到最优解。但需注意，原问题要求的是“最小值等于最大值”的子数组，而上述实现仅统计了连续相同元素的子数组。实际上，两者等价，因为只有连续相同元素的子数组才满足极值相等的条件。
2. 边界条件与优化
在实际应用中，需考虑以下边界条件：
- 空数组：直接返回0
- 单元素数组：返回1
- 所有元素相同：返回
n*(n+1)/2 - 所有元素不同：返回
n（每个单元素子数组）
此外，可通过提前终止优化处理某些特殊情况。例如，若数组长度为1，可直接返回1而无需进入循环。
3. 完整代码示例
#include
#include
using namespace std;
int countSubarraysWithEqualMinMax(const vector& arr) {
int n = arr.size();
if (n == 0) return 0;
if (n == 1) return 1;
int total = 0;
int start = 0;
for (int i = 1; i arr1 = {1, 1, 1, 2, 2, 3};
cout arr2 = {5, 5, 5, 5};
cout arr3 = {1, 2, 3, 4};
cout 三、算法复杂度分析
时间复杂度：算法仅需一次遍历数组，时间复杂度为O(n)，其中n为数组长度。
空间复杂度：除输入数组外，仅使用常数个额外变量，空间复杂度为O(1)。
四、扩展与变种问题
该问题可进一步扩展为以下变种：
- 允许非连续子数组：此时需统计所有元素相同的子集数量，问题转化为组合数学中的多重集组合问题。
- 动态更新数组：若数组支持动态插入或删除元素，需设计增量式算法以高效维护结果。
- 多维数组：将问题扩展至二维数组，统计所有矩形子区域中极值相等的数量。
例如，对于变种问题1，若数组为[1,1,2,1]，则非连续子数组[1,1]（取第1和第2个1）或[1,1,1]（取第1、2、4个1）也满足条件。此时需使用回溯法或动态规划统计所有可能组合。
五、实际应用场景
该算法在以下领域具有实际应用价值：
- 金融分析：统计价格序列中连续平稳区间的数量，辅助判断市场趋势。
- 信号处理：识别信号中持续不变的片段，用于噪声过滤或特征提取。
- 生物信息学：分析DNA序列中连续重复碱基对的分布模式。
例如，在金融领域，若某股票的分钟级价格数组为[100,100,101,100,100]，则算法可统计出3个连续平稳区间（前两个100、后两个100、单个101），帮助分析师识别价格波动特征。
六、测试与验证
为确保算法正确性，需设计全面的测试用例，包括：
- 常规用例：如
[1,2,2,3]，预期结果为5（[1],[2],[2],[2,2],[3]）。 - 边界用例：空数组、单元素数组、全相同元素数组。
- 极端用例：超大数组（如1e6个元素）、包含极大/极小值的数组。
以下是一个测试函数的实现示例：
#include
void testCountSubarrays() {
assert(countSubarraysWithEqualMinMax({}) == 0);
assert(countSubarraysWithEqualMinMax({5}) == 1);
assert(countSubarraysWithEqualMinMax({7,7,7}) == 6);
assert(countSubarraysWithEqualMinMax({1,2,3,4}) == 4);
assert(countSubarraysWithEqualMinMax({1,1,2,2,1,1}) == 9);
cout 七、总结与展望
本文通过数学建模将原问题转化为连续相同元素块的统计问题，并设计了时间复杂度为O(n)的高效算法。该算法不仅适用于静态数组，还可通过适当修改应用于动态数据流场景。未来研究可进一步探索并行化实现或近似算法，以处理超大规模数据。
关键词：子数组统计、极值相等、双指针法、时间复杂度优化、C++实现
简介：本文详细讨论了如何使用C++高效统计数组中最小值等于最大值的子数组数量。通过数学建模将问题转化为连续相同元素块的统计，设计了时间复杂度为O(n)的双指针算法，并提供了完整代码实现与测试用例。文章还分析了算法的边界条件、扩展变种及实际应用场景。
