使用单调栈来找到每个元素左右第一个比其大的元素索引。左侧数组 left 记录每个元素左边第一个大于它的元素索引,右侧数组 right 记录每个元素右边第一个大于它的元素索引。遍历每个元素,计算以该元素为唯一最大值的子数组数量,公式为 left_count * right_count,其中 left_count 是当前元素到左边界的距离,right_count 是当前元素到右边界的距离。最终汇总所有子数组数量。
import java.util.Stack;
小红有一个长度为n的数组{a1,a2,...,an},如果一个数组有一个唯一的最大值,那么这个数组就是一个好数组。
小红想知道这个数组有多少连续子数组是好数组。
连续子数组是指在原数组中,连续的选择一段元素组成的新数组。
第一行输入一个整数n(1≤n≤105)表示数组中的元素数量。 第二行输入n个整数a1,a2,...,an(1≤ai≤109)表示数组元素。
在一行上输出一个整数,表示有多少连续子数组是好数组。
输入
5
1 2 5 4 5
输出
12
一共有15个子数组,其中[1,2,5,4,5],[2,5,4,5],[5,4,5]不是好数组,因为最大值是5,不是唯一的。