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

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

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>

第 128 场双周赛

biweekly-contest-128

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>