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

For each element <code>nums[i]</code>, we can count the number of valid subarrays ending with it.

For each index <code>i</code>, find the nearest index <code>j</code> on its left <code>(j < i)</code> such that <code>nums[j] < nums[i]</code>. This can be done via a monotonic stack.

For each index <code>i</code>, find the number of indices <code>k</code> in the window <code>[j + 1, i]</code> such that <code>nums[k] == nums[i]</code>, this is the number of the valid subarrays ending with <code>nums[i]</code>. This can be done by sliding window.

Sum the answer of all the indices <code>i</code> to get the final result.

Is it possible to use DSU as an alternate solution?

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>

边界元素是最大值的子数组数目

执行通过

错误解答

超出内存限制

超出输出限制

超出时间限制

执行出错

内部出错

编译出错

超时

Restrictions Failed

给你一个 正 整数数组 nums 。

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

 

示例 1：

输入：nums = [1,4,3,3,2]

输出：6

解释：

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

 * 子数组 [1,4,3,3,2] ，最大元素为 1 ，第一个和最后一个元素都是 1 。
 * 子数组 [1,4,3,3,2] ，最大元素为 4 ，第一个和最后一个元素都是 4 。
 * 子数组 [1,4,3,3,2] ，最大元素为 3 ，第一个和最后一个元素都是 3 。
 * 子数组 [1,4,3,3,2] ，最大元素为 3 ，第一个和最后一个元素都是 3 。
 * 子数组 [1,4,3,3,2] ，最大元素为 2 ，第一个和最后一个元素都是 2 。
 * 子数组 [1,4,3,3,2] ，最大元素为 3 ，第一个和最后一个元素都是 3 。

所以我们返回 6 。

示例 2：

输入：nums = [3,3,3]

输出：6

解释：

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

 * 子数组 [3,3,3] ，最大元素为 3 ，第一个和最后一个元素都是 3 。
 * 子数组 [3,3,3] ，最大元素为 3 ，第一个和最后一个元素都是 3 。
 * 子数组 [3,3,3] ，最大元素为 3 ，第一个和最后一个元素都是 3 。
 * 子数组 [3,3,3] ，最大元素为 3 ，第一个和最后一个元素都是 3 。
 * 子数组 [3,3,3] ，最大元素为 3 ，第一个和最后一个元素都是 3 。
 * 子数组 [3,3,3] ，最大元素为 3 ，第一个和最后一个元素都是 3 。

所以我们返回 6 。

示例 3：

输入：nums = [1]

输出：1

解释：

nums 中只有一个子数组 [1] ，最大元素为 1 ，第一个和最后一个元素都是 1 。

所以我们返回 1 。

 

提示：

 * 1 <= nums.length <= 105
 * 1 <= nums[i] <= 109