有效子数组的数目

难度: Hard

Submission

运行时间: 76 ms

内存: 20.7 MB

class Solution:
    def validSubarrays(self, nums: List[int]) -> int:
        stack = []  # 递减的单调栈
        count = 0  # 有效子数组的数量
        
        for num in nums:
            while stack and num < stack[-1]:
                stack.pop()  # 弹出比当前元素大的元素
            
            if not stack or num >= stack[-1]:
                stack.append(num)  # 将当前元素入栈
                count += len(stack)  # 增加有效子数组的数量
        
        return count

Explain

题解使用了一个递减的单调栈来解决问题。对于每个元素，我们维护一个栈，使得栈中的元素始终保持递减。当遍历到一个新的元素时，我们会将栈顶的元素弹出，直到栈顶元素小于等于当前元素或栈为空。这样做的目的是移除那些不能形成有效子数组的元素。每次入栈后，栈中的元素个数即表示以当前元素为结束点的有效子数组数量，因为栈中的每个元素都可以与当前元素形成一个有效的递减子数组。这个过程中，每个元素最多入栈和出栈一次。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def validSubarrays(self, nums: List[int]) -> int:
        stack = []  # 递减的单调栈
        count = 0  # 有效子数组的数量
        
        for num in nums:
            while stack and num < stack[-1]:
                stack.pop()  # 弹出比当前元素大的元素，因为它们不能形成以当前元素为结尾的有效子数组
            
            if not stack or num >= stack[-1]:
                stack.append(num)  # 将当前元素入栈
                count += len(stack)  # 增加有效子数组的数量，每个栈中的元素都可以与当前元素形成一个有效子数组
        
        return count

Explore

在这个问题中，目的是计算所有有效的递减子数组的数目。递减栈被用来确保栈中的所有元素都能与新的栈顶元素形成有效的递减子数组。如果使用递增栈，那么当一个新元素小于栈顶元素时，这个元素与栈中的任何元素都不能保证形成递减的关系，从而无法满足问题的要求。因此，使用递减栈可以有效地维护和扩展当前的递减子数组，而递增栈则无法完成这一任务。

当当前元素小于栈顶元素时，栈顶元素不能再与后续的新元素形成有效的递减子数组。因此，弹出栈顶元素是为了去除不能继续形成有效递减子数组的阻碍。这样可以保持栈的递减性质，确保所有在栈中的元素都能与栈顶元素形成新的有效递减子数组。这个操作是为了更新栈结构，以便新的元素能够正确地计算其能够形成的有效子数组数量。

每次当一个新元素入栈时，栈中的每个元素都可以与这个新元素形成一个以该新元素为结尾的有效递减子数组。例如，如果栈中已有元素是 [3, 2], 当新元素 1 入栈后，可以形成 [3, 2, 1], [2, 1], 和 [1] 三个有效子数组。因此，每次新元素入栈后，增加的有效子数组数量正好等于栈的深度（即栈中元素的数量）。这种计算方式确保了每个可能的递减子数组都被正确地计数。

题解算法中确实考虑了数组中存在相同元素的情况。当遇到相同的元素时，由于题解中允许等于情况也保持元素在栈中，这意味着相同元素也会被推入栈。这样，即使是相同的元素也能形成有效的递减子数组。例如，对于序列 [2, 2], 当第二个2处理时，由于它等于栈顶元素，也会被推入栈中，相应地，有效子数组的计数会增加栈的当前大小。这种处理确保了相同元素的递减子数组也被正确统计。