2026-04-03：统计稳定子数组的数目。用go语言，给你一个整数数组 nums。 如果对某个连续子数组 nums[l..r] 来说，它内部不存在“逆序对”，也就是没有下标满足 i ＜ j 且 nu

2026-04-03统计稳定子数组的数目。用go语言给你一个整数数组 nums。如果对某个连续子数组 nums[l…r] 来说它内部不存在“逆序对”也就是没有下标满足 i j 且 nums[i] nums[j]那么这个子数组称为“稳定子数组”。单个元素的子数组也算稳定。另外给你一组查询 queries每个查询是一个区间 [li, ri]。对每个查询你要统计所有完全落在 nums[li…ri] 范围内的稳定子数组的数量。请把每个查询的结果按顺序放入数组 ans 中并返回ans[i] 表示区间 [li, ri] 内稳定子数组的个数。1 nums.length 100000。1 nums[i] 100000。1 queries.length 100000。queries[i] [li, ri]。0 li ri nums.length - 1。输入nums [3,1,2], queries [[0,1],[1,2],[0,2]]。输出[2,3,4]。解释对于 queries[0] [0, 1]子数组为 [nums[0], nums[1]] [3, 1]。稳定子数组包括 [3] 和 [1]。稳定子数组的总数为 2。对于 queries[1] [1, 2]子数组为 [nums[1], nums[2]] [1, 2]。稳定子数组包括 [1]、[2] 和 [1, 2]。稳定子数组的总数为 3。对于 queries[2] [0, 2]子数组为 [nums[0], nums[1], nums[2]] [3, 1, 2]。稳定子数组包括 [3]、[1]、[2] 和 [1, 2]。稳定子数组的总数为 4。因此ans [2, 3, 4]。题目来自力扣3748。详细步骤解析一、核心概念理解稳定子数组连续子数组内部完全递增/非递减无逆序对单个元素天然是稳定子数组。问题要求对每个查询区间[l, r]统计完全落在该区间内的所有稳定子数组的总数。数据规模数组长度和查询数量都达到 10 万级别必须用O(n) 预处理 O(1) 单次查询的算法暴力枚举会超时。二、算法整体流程分4大步骤步骤1预处理「递增段」与「前缀和数组」稳定子数组的本质是最长非递减连续子段的子数组我们先把原数组拆分成若干个连续的非递减递增段这是计算的基础。遍历数组标记以每个位置为右端点的稳定子数组数量从左到右遍历数组维护一个计数器cnt如果当前元素 ≥ 前一个元素说明还在同一个递增段内cnt加 1如果当前元素 前一个元素说明递增段断开cnt重置为 1新段的起点cnt的含义以当前下标为右端点的稳定子数组的个数。示例nums [3,1,2]下标03cnt1只有[3]下标11 3cnt1只有[1]下标22 ≥ 1cnt2[2]、[1,2]计算前缀和数组sum前缀和数组的作用快速计算任意区间内所有稳定子数组的总数。sum[i]表示数组前i个元素下标0~i-1中所有稳定子数组的总数。递推规则sum[i1] sum[i] cnt累加每个位置的cnt值。示例sum [0, 1, 2, 4]步骤2预处理「下一个递增段起点」数组nxt为了快速判断查询区间是否跨了多个递增段预处理一个数组nxtnxt[i]表示下标i所在递增段的下一个递增段的第一个下标如果是最后一段值为数组长度n。计算方式从右向左遍历数组最后一个元素的nxt直接设为数组长度n如果当前元素 ≤ 下一个元素说明和下一个元素同段nxt[i] nxt[i1]如果当前元素 下一个元素说明段在这里断开nxt[i] i1下一个位置就是新段起点。示例nums [3,1,2]nxt[2] 3数组长度1 ≤ 2 → nxt[1] nxt[2] 33 1 → nxt[0] 1步骤3处理每个查询计算结果对每个查询[l, r]分两种情况计算核心逻辑查询区间内的稳定子数组只能是各个递增段内部的子数组跨段的子数组一定有逆序对不是稳定子数组。情况1查询区间在同一个递增段内判断条件nxt[l] r从l出发的下一个段起点超过了查询右边界r计算方式长度为m r-l1的连续递增段稳定子数组总数 m*(m1)/2等差数列求和公式。情况2查询区间跨了多个递增段判断条件nxt[l] ≤ r查询区间被分成两段[l, nxt[l]-1]和[nxt[l], r]第一段[l, nxt[l]-1]是完整的递增段用公式m*(m1)/2计算m为段长度第二段[nxt[l], r]直接用前缀和数组快速计算总数sum[r1] - sum[nxt[l]]总结果 第一段数量 第二段数量。步骤4示例验证nums[3,1,2]queries[[0,1],[1,2],[0,2]]查询[0,1]nxt[0]1 ≤1跨段第一段[0,0]1*2/21第二段[1,1]sum[2]-sum[1]1结果112查询[1,2]nxt[1]32同段长度22*3/23结果3查询[0,2]nxt[0]1 ≤2跨段第一段[0,0]1第二段[1,2]sum[3]-sum[1]3结果134最终结果[2,3,4]与题目一致。三、时间复杂度与额外空间复杂度1. 总时间复杂度预处理前缀和数组O(n)遍历一次数组预处理nxt数组O(n)反向遍历一次数组处理所有查询O(q)q为查询数量每个查询O(1)计算总时间复杂度O(n q)完美适配 10 万级别的数据规模效率极高。2. 总额外空间复杂度前缀和数组sum长度 n1占用 O(n) 空间nxt数组长度 n占用 O(n) 空间答案数组长度 q占用 O(q) 空间总额外空间复杂度O(n q)除了输入输出外仅使用了线性空间无额外冗余空间。总结算法核心拆分递增段 前缀和预处理 快速查询解决大数据量下的暴力超时问题计算逻辑严格区分查询区间是否跨递增段分别用公式/前缀和计算效率时间 O(nq)、空间 O(nq)完全满足题目 10 万级数据的要求。Go完整代码如下packagemainimport(fmt)funccountStableSubarrays(nums[]int,queries[][]int)[]int64{n:len(nums)// 计算递增子数组个数的前缀和sum:make([]int64,n1)cnt:0fori,x:rangenums{ifi0xnums[i-1]{cnt0}cnt// 现在 cnt 表示以 i 为右端点的递增子数组个数sum[i1]sum[i]int64(cnt)}// nxt[i] 表示 i 右边下一个递增段的左端点若不存在则为 nnxt:make([]int,n)nxt[n-1]nfori:n-2;i0;i--{ifnums[i]nums[i1]{nxt[i]nxt[i1]}else{nxt[i]i1}}ans:make([]int64,len(queries))fork,q:rangequeries{l,r:q[0],q[1]l2:nxt[l]ifl2r{// l 和 r 在同一个区间m:int64(r-l1)ans[k]m*(m1)/2}else{// l 和 r 在不同区间// 分成 [l, l2) [l2, r]// 由于 [l2, r] 中的每个右端点所在递增段的左端点都在 [l2, r] 内所以可以用前缀和计算m:int64(l2-l)ans[k]m*(m1)/2sum[r1]-sum[l2]}}returnans}funcmain(){nums:[]int{3,1,2}queries:[][]int{{0,1},{1,2},{0,2}}result:countStableSubarrays(nums,queries)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-defcount_stable_subarrays(nums,queries):nlen(nums)# 计算递增子数组个数的前缀和sum_prefix[0]*(n1)cnt0fori,xinenumerate(nums):ifi0andxnums[i-1]:cnt0cnt1# 现在 cnt 表示以 i 为右端点的递增子数组个数sum_prefix[i1]sum_prefix[i]cnt# nxt[i] 表示 i 右边下一个递增段的左端点若不存在则为 nnxt[0]*n nxt[n-1]nforiinrange(n-2,-1,-1):ifnums[i]nums[i1]:nxt[i]nxt[i1]else:nxt[i]i1ans[]forl,rinqueries:l2nxt[l]ifl2r:# l 和 r 在同一个区间mr-l1ans.append(m*(m1)//2)else:# l 和 r 在不同区间# 分成 [l, l2) [l2, r]# 由于 [l2, r] 中的每个右端点所在递增段的左端点都在 [l2, r] 内所以可以用前缀和计算ml2-l ans.append(m*(m1)//2sum_prefix[r1]-sum_prefix[l2])returnansif__name____main__:nums[3,1,2]queries[[0,1],[1,2],[0,2]]resultcount_stable_subarrays(nums,queries)print(result)C完整代码如下#includeiostream#includevector#includealgorithmusingnamespacestd;vectorlonglongcountStableSubarrays(vectorintnums,vectorvectorintqueries){intnnums.size();// 计算递增子数组个数的前缀和vectorlonglongsum(n1,0);intcnt0;for(inti0;in;i){if(i0nums[i]nums[i-1]){cnt0;}cnt;// 现在 cnt 表示以 i 为右端点的递增子数组个数sum[i1]sum[i]cnt;}// nxt[i] 表示 i 右边下一个递增段的左端点若不存在则为 nvectorintnxt(n,0);nxt[n-1]n;for(intin-2;i0;i--){if(nums[i]nums[i1]){nxt[i]nxt[i1];}else{nxt[i]i1;}}vectorlonglongans(queries.size(),0);for(intk0;kqueries.size();k){intlqueries[k][0],rqueries[k][1];intl2nxt[l];if(l2r){// l 和 r 在同一个区间longlongmr-l1;ans[k]m*(m1)/2;}else{// l 和 r 在不同区间// 分成 [l, l2) [l2, r]// 由于 [l2, r] 中的每个右端点所在递增段的左端点都在 [l2, r] 内所以可以用前缀和计算longlongml2-l;ans[k]m*(m1)/2sum[r1]-sum[l2];}}returnans;}intmain(){vectorintnums{3,1,2};vectorvectorintqueries{{0,1},{1,2},{0,2}};vectorlonglongresultcountStableSubarrays(nums,queries);cout[;for(inti0;iresult.size();i){if(i0)cout ;coutresult[i];}cout]endl;return0;}