版权声明：本文为博主原创文章遵循 版权协议，转载请附上原文出处链接和本声明

【题目】给定数组arr和整数num，共返回有多少个子数组满足如下情况：

【要求】 如果数組长度为N, 实现时间复杂度为O(N)

1.生成两个双端队列qmax和qmin 生成两个整型变量i和j，表示子数组的范围即arr[i…j]。生成整型变量res表示所有满足条件的子數组数量

2.令j不断向右移动，并不断更新qmax和qmin保证qmax和qmin始终维持动态窗口最大值和小于最小值大于最大值的更新结构。一旦arr[j-i]不满足条件j停圵向右扩。此时arr[i…j-1]、arr[i…j-2]…arr[i…i]一定都是满足条件的也就是说必须以arr[i]作为第一个元素的子数组，满足条件的数量为j-i个于是令res+=j-i。

3.当进行完步驟2令i向右移动一个位置，并对qmax和qmin做出相应的更新qmax和qmin从原来的arr[i…j]窗口变成arr[i+1…j]窗口的最大值和小于最小值大于最大值的更新结构。然后重複步骤2.也就是求必须以arr[i+1]作为第一个元素的子数组中满足条件的数量有多少个。

4.根据步骤2和步骤3依次求出arr[0],…arr[N-1]作为第一个元素的子数组中滿足条件的数量分别有多少个，累加起来就是最终的结果