1063：有效子数组的数目（★★）

力扣第 1063 题

题目

给定一个整数数组 nums ，返回满足下面条件的 非空、连续 子数组的数目：

• 子数组 是数组的 连续 部分。
• 子数组最左边的元素不大于子数组中的其他元素 。

示例 1：

输入：nums = [1,4,2,5,3]
输出：11
解释：有 11 个有效子数组，分别是：[1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3] 。

示例 2：

输入：nums = [3,2,1]
输出：3
解释：有 3 个有效子数组，分别是：[3],[2],[1] 。

示例 3：

输入：nums = [2,2,2]
输出：6
解释：有 6 个有效子数组，分别为是：[2],[2],[2],[2,2],[2,2],[2,2,2] 。

提示：

• 1 <= nums.length <= 5 * 104
• 0 <= nums[i] <= 105

分析

• 为了方便，将 nums 反转得到 A
• 枚举 A[j] 为子数组末尾，找到上一个更小的元素 A[i]，那么 [i+1:j] 开头都可以
• 找上一个更小元素即是典型的单调栈

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def validSubarrays(self, nums: List[int]) -> int:
        A = nums[::-1]
        sk = []
        res = 0
        for j,a in enumerate(A):
            while sk and A[sk[-1]]>=a:
                sk.pop()
            i = sk[-1] if sk else -1
            res += j-i
            sk.append(j)
        return res

54 ms