find-the-number-of-subarrays-where-boundary-elements-are-maximum

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an array of positive integers <code>nums</code>.

Return the number of subarrays of <code>nums</code>, where the first and the last elements of the subarray are equal to the largest element in the subarray.

&nbsp;
Example 1:

<div class="example-block">
Input: nums = [1,4,3,3,2]

Output: 6

Explanation:

There are 6 subarrays which have the first and the last elements equal to the largest element of the subarray:

<ul>
	<li>subarray <code>[1,4,3,3,2]</code>, with its largest element 1. The first element is 1 and the last element is also 1.</li>
	<li>subarray <code>[1,4,3,3,2]</code>, with its largest element 4. The first element is 4 and the last element is also 4.</li>
	<li>subarray <code>[1,4,3,3,2]</code>, with its largest element 3. The first element is 3 and the last element is also 3.</li>
	<li>subarray <code>[1,4,3,3,2]</code>, with its largest element 3. The first element is 3 and the last element is also 3.</li>
	<li>subarray <code>[1,4,3,3,2]</code>, with its largest element 2. The first element is 2 and the last element is also 2.</li>
	<li>subarray <code>[1,4,3,3,2]</code>, with its largest element 3. The first element is 3 and the last element is also 3.</li>
</ul>

Hence, we return 6.
</div>

Example 2:

<div class="example-block">
Input: nums = [3,3,3]

Output: 6

Explanation:

There are 6 subarrays which have the first and the last elements equal to the largest element of the subarray:

<ul>
	<li>subarray <code>[3,3,3]</code>, with its largest element 3. The first element is 3 and the last element is also 3.</li>
	<li>subarray <code>[3,3,3]</code>, with its largest element 3. The first element is 3 and the last element is also 3.</li>
	<li>subarray <code>[3,3,3]</code>, with its largest element 3. The first element is 3 and the last element is also 3.</li>
	<li>subarray <code>[3,3,3]</code>, with its largest element 3. The first element is 3 and the last element is also 3.</li>
	<li>subarray <code>[3,3,3]</code>, with its largest element 3. The first element is 3 and the last element is also 3.</li>
	<li>subarray <code>[3,3,3]</code>, with its largest element 3. The first element is 3 and the last element is also 3.</li>
</ul>

Hence, we return 6.
</div>

Example 3:

<div class="example-block">
Input: nums = [1]

Output: 1

Explanation:

There is a single subarray of <code>nums</code> which is <code>[1]</code>, with its largest element 1. The first element is 1 and the last element is also 1.

Hence, we return 1.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
</ul>

numberOfSubarrays

Find the Number of Subarrays Where Boundary Elements Are Maximum

Number of Subarrays with Bounded Maximum

number-of-subarrays-with-bounded-maximum

区间子数组个数

Count Subarrays With Fixed Bounds

count-subarrays-with-fixed-bounds

统计定界子数组的数目

Count Subarrays Where Max Element Appears at Least K Times

count-subarrays-where-max-element-appears-at-least-k-times

统计最大元素出现至少 K 次的子数组

Stack

Array

Binary Search

Monotonic Stack

给你一个 正&nbsp;整数数组&nbsp;<code>nums</code>&nbsp;。

请你求出&nbsp;<code>nums</code>&nbsp;中有多少个子数组，满足子数组中&nbsp;第一个&nbsp;和 最后一个&nbsp;元素都是这个子数组中的 最大&nbsp;值。

&nbsp;

示例 1：

<div class="example-block">
输入：nums = [1,4,3,3,2]

输出：6

解释：

总共有 6 个子数组满足第一个元素和最后一个元素都是子数组中的最大值：

<ul>
	<li>子数组&nbsp;<code>[1,4,3,3,2]</code>&nbsp;，最大元素为 1 ，第一个和最后一个元素都是 1 。</li>
	<li>子数组&nbsp;<code>[1,4,3,3,2]</code>&nbsp;，最大元素为 4 ，第一个和最后一个元素都是 4 。</li>
	<li>子数组&nbsp;<code>[1,4,3,3,2]</code>&nbsp;，最大元素为 3 ，第一个和最后一个元素都是 3 。</li>
	<li>子数组&nbsp;<code>[1,4,3,3,2]</code>&nbsp;，最大元素为 3 ，第一个和最后一个元素都是 3 。</li>
	<li>子数组&nbsp;<code>[1,4,3,3,2]</code>&nbsp;，最大元素为 2 ，第一个和最后一个元素都是 2 。</li>
	<li>子数组&nbsp;<code>[1,4,3,3,2]</code>&nbsp;，最大元素为 3 ，第一个和最后一个元素都是 3 。</li>
</ul>

所以我们返回 6 。
</div>

示例 2：

<div class="example-block">
输入：nums = [3,3,3]

输出：6

解释：

总共有 6 个子数组满足第一个元素和最后一个元素都是子数组中的最大值：

<ul>
	<li>子数组 <code>[3,3,3]</code>&nbsp;，最大元素为 3&nbsp;，第一个和最后一个元素都是 3&nbsp;。</li>
	<li>子数组 <code>[3,3,3]</code>&nbsp;，最大元素为 3&nbsp;，第一个和最后一个元素都是 3&nbsp;。</li>
	<li>子数组 <code>[3,3,3]</code>&nbsp;，最大元素为 3&nbsp;，第一个和最后一个元素都是 3&nbsp;。</li>
	<li>子数组 <code>[3,3,3]</code>&nbsp;，最大元素为 3&nbsp;，第一个和最后一个元素都是 3&nbsp;。</li>
	<li>子数组 <code>[3,3,3]</code>&nbsp;，最大元素为 3&nbsp;，第一个和最后一个元素都是 3&nbsp;。</li>
	<li>子数组 <code>[3,3,3]</code>&nbsp;，最大元素为 3&nbsp;，第一个和最后一个元素都是 3&nbsp;。</li>
</ul>

所以我们返回 6 。
</div>

示例 3：

<div class="example-block">
输入：nums = [1]

输出：1

解释：

<code>nums</code>&nbsp;中只有一个子数组&nbsp;<code>[1]</code>&nbsp;，最大元素为 1 ，第一个和最后一个元素都是 1 。

所以我们返回 1 。
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
</ul>