以索引 i 开始或结束的子数组的计数 使得 arr[i] 在子数组中是最大值

Question

在解题时，我们需要找到一个数组中以每个索引 i 开始或结束的子数组中最大值为 arr[i] 的子数组的数量。

解题思路

我们可以分别遍历数组，找到以每个索引 i 为结尾的子数组的最大值，以及以每个索引 i 为开头的子数组的最大值。接着，我们可以使用动态规划的方法，记录以每个索引 i 结尾的子数组的数量，以及以每个索引 i 开头的子数组的数量。最后，将这两个计数相乘，就可以得到以每个索引 i 开始或结束的子数组中最大值为 arr[i] 的子数组的数量。

具体实现可参考以下示例代码：

def countSubarrays(arr):
    n = len(arr)
    left = [1] * n # 以每个索引 i 开头的子数组的数量
    right = [1] * n # 以每个索引 i 结尾的子数组的数量

    # 计算以每个索引 i 开头的子数组的数量
    for i in range(1, n):
        j = i - 1
        while j >= 0 and arr[j] > arr[i]:
            left[i] += left[j]
            j -= left[j]

    # 计算以每个索引 i 结尾的子数组的数量
    for i in range(n - 2, -1, -1):
        j = i + 1
        while j < n and arr[j] > arr[i]:
            right[i] += right[j]
            j += right[j]

    # 计算以每个索引 i 开始或结束的子数组中最大值为 arr[i] 的子数组的数量
    ans = 0
    for i in range(n):
        ans += left[i] * right[i]

    return ans

总结

以索引 i 开始或结束的子数组的计数，使得 arr[i] 在子数组中是最大值，可以使用动态规划的方法来实现。具体思路是先分别遍历数组，找到以每个索引 i 为结尾的子数组的最大值，以及以每个索引 i 为开头的子数组的最大值。然后，使用动态规划的方法记录以每个索引 i 结尾的子数组的数量，以及以每个索引 i 开头的子数组的数量。最后，将这两个计数相乘，就可以得到以每个索引 i 开始或结束的子数组中最大值为 arr[i] 的子数组的数量。