How do I optimize the solution for the problem 'Find the Number of Subarrays Where Boundary Elements Are Maximum'?

You can use binary search over the valid answer space combined with stack-based techniques to efficiently count valid subarrays.

What is the time complexity for this problem?

The time complexity depends on the approach used. Binary search combined with a stack can offer a more efficient solution than brute force.

How does a monotonic stack help in solving this problem?

A monotonic stack helps in efficiently counting subarrays by tracking the valid subarrays ending at each element while ensuring the boundaries are the largest.

What are the common mistakes in solving this problem?

Common mistakes include missing boundary element checks, using brute force without optimization, and misunderstanding the sliding window or stack approach.

Can I apply this problem's solution to other types of array-based subarray counting problems?

Yes, the binary search and stack-based techniques can be applied to similar problems that involve counting subarrays with specific properties.

#3113

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

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

给你一个正整数数组 nums 。请你求出 nums 中有多少个子数组，满足子数组中第一个和最后一个元素都是这个子数组中的最大值。示例 1：输入： nums = [1,4,3,3,2] 输出： 6 解释：总共有 6 个子数组满足第一个元素和最后一个元素都是子数组中的最大值：子…

数组二分查找栈单调栈

题目描述

给你一个正整数数组 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 <= 10⁵
1 <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：单调栈

我们考虑以数组 $nums$ 中的每个元素 $x$ 作为子数组的边界元素且最大值的情况。

每个长度为 $1$ 的子数组都满足条件，而对于长度大于 $1$ 的子数组，子数组中的所有元素都不能大于边界元素 $x$ ，我们可以用单调栈来实现。

我们维护一个从栈底到栈顶单调递减的栈，单调栈的每个元素是一个二元组 $[x, cnt]$ ，表示元素 $x$ 且以 $x$ 为边界元素且最大值的子数组的个数为 $cnt$ 。

我们从左到右遍历数组 $nums$ ，对于每个元素 $x$ ，我们不断地将栈顶元素弹出，直到栈为空或者栈顶元素的第一个元素大于等于 $x$ 。如果栈为空，或者栈顶元素的第一个元素大于 $x$ ，说明当前遇到第一个边界元素为 $x$ 且最大值的子数组，该子数组的长度为 $1$ ，所以我们将 $[x, 1]$ 入栈。如果栈顶元素的第一个元素等于 $x$ ，说明当前遇到的边界元素为 $x$ 且最大值的子数组，我们将栈顶元素的第二个元素加 $1$ 。然后，我们将栈顶元素的第二个元素加到答案中。

遍历结束后，返回答案即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def numberOfSubarrays(self, nums: List[int]) -> int:
        stk = []
        ans = 0
        for x in nums:
            while stk and stk[-1][0] < x:
                stk.pop()
            if not stk or stk[-1][0] > x:
                stk.append([x, 1])
            else:
                stk[-1][1] += 1
            ans += stk[-1][1]
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ability to optimize brute force solutions using binary search and stacks.
question_mark
Understanding of monotonic stacks for tracking subarray boundaries.
question_mark
Skill in reducing time complexity by focusing on valid subarray counts.

warning

常见陷阱

外企场景

error
Ignoring the need to check both the first and last elements of the subarray during counting.
error
Relying on brute force counting without optimizing using binary search or stack methods.
error
Misunderstanding the boundary conditions when using sliding window techniques.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Variation with larger subarrays or larger input sizes.
arrow_right_alt
Handling arrays with repeated values efficiently.
arrow_right_alt
Different ways to approach the binary search or stack-based optimization.

help

常见问题

外企场景

继续练习

#2945 找到最大非递减数组的长度 #2940 找到 Alice 和 Bob 可以相遇的建筑 #2736 最大和查询