Hard

题目描述

给你一个正整数数组 nums。

返回 nums 的子数组数量，其中子数组的第一个和最后一个元素都等于该子数组中的最大元素。

示例 1：

输入：nums = [1,4,3,3,2]
输出：6
解释：
有 6 个子数组的第一个和最后一个元素都等于子数组中的最大元素：
- 子数组 [1]，最大元素为 1。第一个元素是 1，最后一个元素也是 1。
- 子数组 [4]，最大元素为 4。第一个元素是 4，最后一个元素也是 4。
- 子数组 [3]，最大元素为 3。第一个元素是 3，最后一个元素也是 3。
- 子数组 [3]，最大元素为 3。第一个元素是 3，最后一个元素也是 3。
- 子数组 [2]，最大元素为 2。第一个元素是 2，最后一个元素也是 2。
- 子数组 [3,3]，最大元素为 3。第一个元素是 3，最后一个元素也是 3。

示例 2：

输入：nums = [3,3,3]
输出：6

示例 3：

输入：nums = [1]
输出：1

约束条件：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

解题思路

解题思路

这道题要求找到所有满足条件的子数组：子数组的首尾元素都等于该子数组的最大值。

关键观察：如果一个子数组的首尾元素都是最大值，那么这个子数组中所有元素都不能大于首尾元素的值。

核心思路：

  1. 对于每个位置 i，计算以 nums[i] 结尾的有效子数组数量
  2. 使用单调栈找到每个位置左侧第一个小于当前元素的位置
  3. 在有效区间内统计与当前元素相等的元素个数

算法步骤：

  1. 使用单调递减栈，对于每个位置 i，找到左侧第一个严格小于 nums[i] 的位置 j
  2. 在区间 [j+1, i] 内，统计有多少个位置的值等于 nums[i]
  3. 这些位置都可以作为有效子数组的起点，以 i 为终点

优化： 可以结合滑动窗口技术，在遍历过程中维护相等元素的计数，避免重复计算。

时间复杂度为 O(n)，空间复杂度为 O(n)，其中 n 是数组长度。

代码实现

class Solution {
public:
    long long numberOfSubarrays(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n, -1);
        stack<int> st;
        
        // 找到每个位置左侧第一个小于当前元素的位置
        for (int i = 0; i < n; i++) {
            while (!st.empty() && nums[st.top()] >= nums[i]) {
                st.pop();
            }
            if (!st.empty()) {
                left[i] = st.top();
            }
            st.push(i);
        }
        
        long long result = 0;
        for (int i = 0; i < n; i++) {
            int start = left[i] + 1;
            int count = 0;
            // 统计区间 [start, i] 中等于 nums[i] 的元素个数
            for (int j = start; j <= i; j++) {
                if (nums[j] == nums[i]) {
                    count++;
                }
            }
            result += count;
        }
        
        return result;
    }
};

class Solution:
    def numberOfSubarrays(self, nums: List[int]) -> int:
        n = len(nums)
        left = [-1] * n
        stack = []
        
        # 找到每个位置左侧第一个小于当前元素的位置
        for i in range(n):
            while stack and nums[stack[-1]] >= nums[i]:
                stack.pop()
            if stack:
                left[i] = stack[-1]
            stack.append(i)
        
        result = 0
        for i in range(n):
            start = left[i] + 1
            count = 0
            # 统计区间 [start, i] 中等于 nums[i] 的元素个数
            for j in range(start, i + 1):
                if nums[j] == nums[i]:
                    count += 1
            result += count
        
        return result

public class Solution {
    public long NumberOfSubarrays(int[] nums) {
        int n = nums.Length;
        int[] left = new int[n];
        for (int i = 0; i < n; i++) {
            left[i] = -1;
        }
        Stack<int> stack = new Stack<int>();
        
        // 找到每个位置左侧第一个小于当前元素的位置
        for (int i = 0; i < n; i++) {
            while (stack.Count > 0 && nums[stack.Peek()] >= nums[i]) {
                stack.Pop();
            }
            if (stack.Count > 0) {
                left[i] = stack.Peek();
            }
            stack.Push(i);
        }
        
        long result = 0;
        for (int i = 0; i < n; i++) {
            int start = left[i] + 1;
            int count = 0;
            // 统计区间 [start, i] 中等于 nums[i] 的元素个数
            for (int j = start; j <= i; j++) {
                if (nums[j] == nums[i]) {
                    count++;
                }
            }
            result += count;
        }
        
        return result;
    }
}

var numberOfSubarrays = function(nums) {
    const n = nums.length;
    let count = 0;
    
    for (let i = 0; i < n; i++) {
        let max = nums[i];
        for (let j = i; j < n; j++) {
            max = Math.max(max, nums[j]);
            if (nums[i] === max && nums[j] === max) {
                count++;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)外层循环 O(n)，内层统计循环最坏情况 O(n)
空间复杂度O(n)单调栈和 left 数组的空间开销

相关题目