1063. 有效子数组的数目

Difficulty
Hard
Tags
单调栈
URL
https://leetcode.cn/problems/number-of-valid-subarrays/
Star
  • 子数组 是数组的 连续 部分。
  • 子数组最左边的元素不大于子数组中的其他元素 。
示例 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

法 1 单调栈

思路
以每个 num为起点，计算该起点的子数字数量。子数组数量取决于终点，而终点是第一个小于 num的前一个数字 所以本题就是 找每个数字 右边比它小的数字的下标。
题解
class Solution:
    def validSubarrays(self, nums: List[int]) -> int:
        # 以每个 num为起点，计算该起点的子数字数量
        # 子数组数量取决于终点，而终点是第一个小于 num的前一个数字
        # 所以本题就是 找每个数字 右边比它小的下标。
        stack = []
        res = [1 for _ in nums]
        for i in range(len(nums)-1, -1, -1):
            while stack and nums[i] <= nums[stack[-1]]:
                stack.pop()

            if stack:
                res[i] = stack[-1] - i
            else:
                res[i] = len(nums) - i
            stack.append(i)   
    
        return sum(res)