思路:单调栈 + 枚举

使用单调栈来找到每个元素左右第一个比其大的元素索引。左侧数组 left 记录每个元素左边第一个大于它的元素索引，右侧数组 right 记录每个元素右边第一个大于它的元素索引。遍历每个元素，计算以该元素为唯一最大值的子数组数量，公式为 left_count * right_count，其中 left_count 是当前元素到左边界的距离，right_count 是当前元素到右边界的距离。最终汇总所有子数组数量。

代码

java

import java.util.Stack;

public class Main {
    public static long countGoodSubarrays(int n, int[] a) {
        long totalGoodSubarrays = 0;
        int[] left = new int[n];  // 左侧第一个比 a[i] 大的元素的索引
        int[] right = new int[n]; // 右侧第一个比 a[i] 大的元素的索引
        
        Stack<Integer> stack = new Stack<>();
        
        // 计算每个元素左侧第一个大于等于它的元素
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && a[stack.peek()] < a[i]) {
                stack.pop();
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek(); // -1 表示没有比 a[i] 大的元素
            stack.push(i);
        }

        // 清空栈以计算右侧的第一个大于等于它的元素
        stack.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && a[stack.peek()] < a[i]) {
                stack.pop();
            }
            right[i] = stack.isEmpty() ? n : stack.peek(); // n 表示没有比 a[i] 大的元素
            stack.push(i);
        }

        // 计算好数组数量
        for (int i = 0; i < n; i++) {
            int leftCount = i - left[i];  // 从 left[i] 到 i 的子数组数量
            int rightCount = right[i] - i; // 从 i 到 right[i] 的子数组数量
            totalGoodSubarrays += leftCount * rightCount;
        }

        return totalGoodSubarrays;
    }

    public static void main(String[] args) {
        java.util.Scanner scanner = new java.util.Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        long result = countGoodSubarrays(n, a);
        System.out.println(result);
        scanner.close();
    }
}

python

def count_good_subarrays(n, a):
    # 初始化
    total_good_subarrays = 0
    left = [-1] * n  # 左侧第一个比 a[i] 大的元素的索引
    right = [n] * n  # 右侧第一个比 a[i] 大的元素的索引

    # 计算每个元素左侧第一个大于等于它的元素
    stack = []
    for i in range(n):
        while stack and a[stack[-1]] < a[i]:
            stack.pop()
        left[i] = stack[-1] if stack else -1  # -1 表示没有比 a[i] 大的元素
        stack.append(i)

    # 清空栈以计算右侧的第一个大于等于它的元素
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and a[stack[-1]] < a[i]:
            stack.pop()
        right[i] = stack[-1] if stack else n  # n 表示没有比 a[i] 大的元素
        stack.append(i)
    # 计算好数组数量
    for i in range(n):
        left_count = i - left[i]  # 从 left[i] 到 i 的子数组数量
        right_count = right[i] - i  # 从 i 到 right[i] 的子数组数量
        total_good_subarrays += left_count * right_count

    return total_good_subarrays

# 输入处理
n = int(input())
a = list(map(int, input().split()))

# 调用函数并输出结果
result = count_good_subarrays(n, a)
print(result)

cpp

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

long long countGoodSubarrays(int n, vector<int>& a) {
    long long totalGoodSubarrays = 0;
    vector<int> left(n, -1);  // 左侧第一个比 a[i] 大的元素的索引
    vector<int> right(n, n);  // 右侧第一个比 a[i] 大的元素的索引

    stack<int> st;

    // 计算每个元素左侧第一个大于等于它的元素
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) {
            st.pop();
        }
        left[i] = st.empty() ? -1 : st.top(); // -1 表示没有比 a[i] 大的元素
        st.push(i);
    }

    // 清空栈以计算右侧的第一个大于等于它的元素
    while (!st.empty()) st.pop(); // 清空栈
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && a[st.top()] < a[i]) {
            st.pop();
        }
        right[i] = st.empty() ? n : st.top(); // n 表示没有比 a[i] 大的元素
        st.push(i);
    }

    // 计算好数组数量
    for (int i = 0; i < n; i++) {
        long long leftCount = i - left[i];  // 从 left[i] 到 i 的子数组数量
        long long rightCount = right[i] - i; // 从 i 到 right[i] 的子数组数量
        totalGoodSubarrays += leftCount * rightCount;
    }

    return totalGoodSubarrays;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    long long result = countGoodSubarrays(n, a);
    cout << result << endl;

    return 0;
}

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目内容

小红有一个长度为n的数组{$a_1,a_2,...,a_n$},如果一个数组有一个唯一的最大值，那么这个数组就是一个好数组。

小红想知道这个数组有多少连续子数组是好数组。

连续子数组是指在原数组中，连续的选择一段元素组成的新数组。

输入描述

第一行输入一个整数$n$($1≤n≤10^5$)表示数组中的元素数量。 第二行输入$n$个整数$a_1,a_2,...,a_n$($1≤a_i≤10^9$)表示数组元素。

输出描述

在一行上输出一个整数，表示有多少连续子数组是好数组。

样例1

输入

5
1 2 5 4 5

输出

12

说明

一共有$15$个子数组，其中$[1,2,5,4,5],[2, 5,4, 5],[5,4,5]$不是好数组，因为最大值是$5$，不是唯一的。