2026-02-06：碗子数组的数目。用go语言，给定一个元素互不相同的整数数组 nums。把任意一个连续片段 nums[l..r] 记作“碗”，当且仅当满足： - 该片段包含至少三个元素； - 两端

2026-02-06：碗子数组的数目。用go语言，给定一个元素互不相同的整数数组 nums。把任意一个连续片段 nums[l…r] 记作“碗”，当且仅当满足：

• 该片段包含至少三个元素；

• 两端的较小值大于片段中间所有元素（即中间每个数都比两端较小的那个数要小）。

要求统计数组中符合上述条件的连续片段数量。说明：这里的“连续片段”即数组中连续的一段元素序列。

3 <= nums.length <= 100000。

1 <= nums[i] <= 1000000000。

nums 由不同的元素组成。

输入: nums = [2,5,3,1,4]。

输出: 2。

解释:

碗子数组是 [3, 1, 4] 和 [5, 3, 1, 4]。

[3, 1, 4] 是一个碗，因为 min(3, 4) = 3 > max(1) = 1。

[5, 3, 1, 4] 是一个碗，因为 min(5, 4) = 4 > max(3, 1) = 3。

题目来自力扣3676。

算法过程分步解析

1. 初始化与核心数据结构

   • 算法定义了一个名为st的切片（slice），它被初始化为输入切片nums的一个零长度前缀（nums[:0]）。这个st切片将作为一个单调栈（monotonic stack）来使用。栈内预期保存的是数组元素的索引（根据算法逻辑，实际存储的是元素值，但其顺序和索引的单调性相关），并且这个栈是单调递减的，即栈底到栈顶的元素值是递减的。

2. 遍历数组元素

   • 算法使用一个for-range循环，从左到右依次遍历输入数组nums中的每一个元素x（即当前正在处理的元素）。

3. 维护单调栈

   • 在将当前元素x入栈之前，需要一个“出栈”循环来维护栈的单调递减性质。
   • 出栈条件：只要栈不为空（len(st) > 0）并且栈顶元素的值小于当前元素x的值（st[len(st)-1] < x），就需要将栈顶元素弹出。
   • 出栈操作与计数：每当一个栈顶元素被弹出时，算法会进行一次重要的检查：如果此时栈内还有元素（即len(st) > 0），那么就将答案ans加一。这个操作的逻辑是：被弹出的元素（记为mid）、当前栈顶的元素（记为left）和当前正准备入栈的元素x（视为right）三者构成了一个潜在的关系。left是mid左边第一个比它大的元素，x是mid右边第一个比它大的元素。当mid被弹出时，意味着以mid为中间某个元素、以left和x为两端的一个连续片段，满足了“中间的所有元素（至少包含mid）都小于两端中较小的那个”这一条件的一部分。每次弹出都意味着发现了一个以left和x为两端、以刚弹出的mid为中间元素的合格“碗”的组成部分。

4. 当前元素入栈

   • 当栈顶没有比当前元素x更小的元素需要弹出后，或者栈为空时，就将当前元素x压入栈中。这保证了栈的单调递减性。

5. 遍历完成与结果

   • 当循环遍历完数组nums的所有元素后，变量ans中累积的值就是题目所求的“碗子数组”的数量，函数将其返回。

核心逻辑与示例关联

以输入nums = [2, 5, 3, 1, 4]为例，结合题目给出的解释：

• 当处理到元素4时，栈的状态（从底到顶）可能类似于[5, 3, 1]。
• 为了将4入栈，需要弹出比它小的元素1和3。
  • 弹出1时，栈顶是3。此时栈不为空，ans加1。这对应了碗子数组[3, 1, 4]（两端是3和4，min(3,4)=3，中间元素1<3）。
  • 弹出3时，栈顶是5。此时栈不为空，ans再加1。这对应了碗子数组[5, 3, 1, 4]（两端是5和4，min(5,4)=4，中间元素3和1都小于4）。
• 这个计数过程完美地匹配了题目给出的两个碗子数组。

复杂度分析

• 总的时间复杂度：O(n)
  算法主要包含一个遍历数组的循环。虽然内部有一个while循环进行出栈操作，但数组中的每个元素最多只会被压入栈一次和弹出栈一次。因此，整个过程中出栈操作的总次数不会超过n（数组长度）。这属于均摊分析（Amortized Analysis）的概念，可以将每个元素出栈操作的均摊成本视为常数。所以，整个算法的时间复杂度是线性的，即O(n)。

• 总的额外空间复杂度：O(n)
  算法使用的额外空间主要是单调栈st。在最坏情况下，如果输入数组是严格递减的（例如[5, 4, 3, 2, 1]），那么所有元素都会被依次压入栈中而不会被弹出。因此，栈可能需要的最大空间与输入数组的长度n成正比。所以，额外的空间复杂度是O(n)。

Go完整代码如下：

packagemainimport("fmt")funcbowlSubarrays(nums[]int)(ansint64){st:=nums[:0]for_,x:=rangenums{forlen(st)>0&&st[len(st)-1]<x{st=st[:len(st)-1]iflen(st)>0{ans++}}st=append(st,x)}return}funcmain(){nums:=[]int{2,5,3,1,4}result:=bowlSubarrays(nums)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-fromtypingimportListdefbowl_subarrays(nums:List[int])->int:ans=0st=[]# 使用Python列表作为栈forxinnums:# 维护单调栈：弹出所有小于当前元素的栈顶元素whilestandst[-1]<x:st.pop()# 如果弹出后栈非空，增加计数ifst:ans+=1# 当前元素入栈st.append(x)returnansdefmain():nums=[2,5,3,1,4]result=bowl_subarrays(nums)print(result)if__name__=="__main__":main()

C++完整代码如下：

#include<iostream>#include<vector>usingnamespacestd;longlongbowlSubarrays(vector<int>&nums){longlongans=0;vector<int>st;// 使用vector作为栈for(intx:nums){// 维护单调栈：弹出所有小于当前元素的栈顶元素while(!st.empty()&&st.back()<x){st.pop_back();// 如果弹出后栈非空，增加计数if(!st.empty()){ans++;}}// 当前元素入栈st.push_back(x);}returnans;}intmain(){vector<int>nums={2,5,3,1,4};longlongresult=bowlSubarrays(nums);cout<<result<<endl;// 输出结果return0;}