小羊的连续子数组

约 327 字大约 1 分钟

2024-09-29

题目内容

小羊有一个长度为 n 的数组 { a1, a2, ..., an },如果一个数组有一个唯一的最大值，那么这个数组就是一个好数组。小红想知道这个数组有多少连续子数组是好数组。连续子数组是指在原数组中，连续的选择一段元素组成的新数组。

输入描述

第一行输入一个整数 n (1 ≤ n ≤ $$10^5$$)表示数组中的元素数量。第二行输入 n 个整数 a1, a2 ,..., an (1 ≤ ai ≤ $10^9$ )表示数组元素。

输出描述

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

样例1

说明

一共有 15 个子数组，其中有 3 个字数组 [1,2,5,4,5], [2,5,4,5], [5,4,5] 不是好数组，因为它们最大值 5 不是唯一的，所以返回 12。

这道题主要考察候选人对单调栈是否熟悉，属于难题。

⭐️ ⭐️ ⭐️ ⭐️ ⭐️

提示