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. 1. 初始化与核心数据结构
   • • 算法定义了一个名为 st 的切片（slice），它被初始化为输入切片 nums 的一个零长度前缀（nums[:0]）。这个 st 切片将作为一个单调栈（monotonic stack）来使用。栈内预期保存的是数组元素的索引（根据算法逻辑，实际存储的是元素值，但其顺序和索引的单调性相关），并且这个栈是单调递减的，即栈底到栈顶的元素值是递减的。
2. 2. 遍历数组元素
   • • 算法使用一个 for-range 循环，从左到右依次遍历输入数组 nums 中的每一个元素 x（即当前正在处理的元素）。
3. 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. 4. 当前元素入栈
   • • 当栈顶没有比当前元素 x 更小的元素需要弹出后，或者栈为空时，就将当前元素 x 压入栈中。这保证了栈的单调递减性。
5. 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完整代码如下：

.

package main

import (
    "fmt"
)

func bowlSubarrays(nums []int) (ans int64) {
    st := nums[:0]
    for _, x := range nums {
        forlen(st) > 0 && st[len(st)-1] < x {
            st = st[:len(st)-1]
            iflen(st) > 0 {
                ans++
            }
        }
        st = append(st, x)
    }
    return
}

func main() {
    nums := []int{2, 5, 3, 1, 4}
    result := bowlSubarrays(nums)
    fmt.Println(result)
}

在这里插入图片描述

Python完整代码如下：

.

# -*-coding:utf-8-*-

from typing import List

def bowl_subarrays(nums: List[int]) -> int:
    ans = 0
    st = []  # 使用Python列表作为栈
    
    for x in nums:
        # 维护单调栈：弹出所有小于当前元素的栈顶元素
        while st and st[-1] < x:
            st.pop()
            # 如果弹出后栈非空，增加计数
            if st:
                ans += 1
        # 当前元素入栈
        st.append(x)
    
    return ans

def main():
    nums = [2, 5, 3, 1, 4]
    result = bowl_subarrays(nums)
    print(result) 

if __name__ == "__main__":
    main()

在这里插入图片描述

C++完整代码如下：

.

#include <iostream>
#include <vector>
using namespace std;

long long bowlSubarrays(vector<int>& nums) {
    long long ans = 0;
    vector<int> st;  // 使用vector作为栈

    for (int x : nums) {
        // 维护单调栈：弹出所有小于当前元素的栈顶元素
        while (!st.empty() && st.back() < x) {
            st.pop_back();
            // 如果弹出后栈非空，增加计数
            if (!st.empty()) {
                ans++;
            }
        }
        // 当前元素入栈
        st.push_back(x);
    }

    return ans;
}

int main() {
    vector<int> nums = {2, 5, 3, 1, 4};
    long long result = bowlSubarrays(nums);
    cout << result << endl;  // 输出结果
    return0;
}

在这里插入图片描述