[Leetcode 1063] Number of Valid Subarrays

原题说明

Given an array A of integers, return the number of non-empty continuous subarrays that satisfy the following condition:

The leftmost element of the subarray is not larger than other elements in the subarray.

Example 1:

Input: [1,4,2,5,3]
Output: 11
Explanation: There are 11 valid subarrays: [1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3].

Example 2:

Input: [3,2,1]
Output: 3
Explanation: The 3 valid subarrays are: [3],[2],[1].

Example 3:

Input: [2,2,2]
Output: 6
Explanation: There are 6 valid subarrays: [2],[2],[2],[2,2],[2,2],[2,2,2].

Note:

1. 1 <= A.length <= 50000
2. 0 <= A[i] <= 100000

解题思路

建立一个从顶往下递减的栈stk，遍历nums中每个元素num，比较num与栈顶元素大小。
如果num较大，则不断pop栈顶元素，直到栈空或者栈顶元素小于等于num，然后将num插入栈顶。
此时，我们可以以stk中任意元素为开头，以num为结尾组成符合题目条件的subarray，因此
以num为结尾的subarray个数为stk的size。

示例代码 (cpp)

class Solution {
public:
    int validSubarrays(vector<int>& nums) {
        stack<int> stk;
        int count = 0;
        for (const auto num : nums) {
            while (!stk.empty() && num < stk.top()) {
                stk.pop();
            }
            stk.push(num);
            count += stk.size();
        }
        return count;
    }
};

示例代码 (java)

class Solution {
    public int validSubarrays(int[] nums) {
        int res = nums.length;
        if(nums.length <= 1) {
            return res;
        }
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(nums[0]);
        for(int i = 1; i < nums.length; i++) {
            int num = nums[i];
            while(!stack.isEmpty() && num < stack.peek()) {
                stack.pop();
            }
            res += stack.size();
            stack.push(num);
        }
        return res;
    }
}

示例代码 (python)

class Solution:
    def validSubarrays(self, nums: List[int]) -> int:
        stack = []
        nextSmaller = [len(nums)] * len(nums)
        for i, v in enumerate(nums):
            while stack and stack[-1][1] > v:
                nextSmaller[stack.pop()[0]] = i
            stack.append([i, v])
        return sum([v - i for i, v in enumerate(nextSmaller)])

复杂度分析

时间复杂度: O(N)
空间复杂度: O(N)

视频讲解

我们在Youtube上更新了视频讲解，欢迎关注！