题目描述
给你一个 正 整数数组 nums 。
请你求出 nums 中有多少个子数组，满足子数组中 第一个 和 最后一个 元素都是这个子数组中的 最大 值。
思路
最开始是二重循环，用窗口扫描，如果有大的就退出，有等于的就添加：
class Solution:
def numberOfSubarrays(self, nums: List[int]) -> int:
l = len(nums)
ans = 0
for i, num in enumerate(nums):
maxNum = num
ans += 1
for j in range(i+1, l):
if maxNum < nums[j]:
break
if maxNum == nums[j]:
ans += 1
return ans简单，但是 TLE（Sad）。
看了一下题解，可以用单调栈的思想去实现。简单来说是维护一个底大顶小的单调栈，记录元素出现的次数。在遍历数字时，设置当前元素为 num，栈顶元素为 top：
- 如果
num<top，就将num和它出现的次数 1 入栈； - 如果
num>top，就将top出栈直到top>num，再将num入栈； - 如果
num==top，假设栈顶记录出现次数为cnt，那么num可以和左边cnt个num组成cnt个符合要求的子数组，就可以将答案增加cnt，然后将cnt=cnt+1。
在实现的时候可以向栈底增加一个无穷大的哨兵，简化判断逻辑。
在最开始的时候，ans=n，表示每个数字都可以形成一个长度为 1 的子数组。
这样其实还是将问题分成了几个子问题再去求和，以后可以多注意类似情况。
最终代码：
class Solution:
def numberOfSubarrays(self, nums: List[int]) -> int:
ans = len(nums)
stack = [[inf, 0]]
for num in nums:
while num > stack[-1][0]:
stack.pop()
if num == stack[-1][0]:
ans += stack[-1][1]
stack[-1][1] += 1
if num < stack[-1][0]:
stack.append([num, 1])
return ans