# 1063. Number of Valid Subarrays

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public: int validSubarrays(vector& nums) { // For each num in nums, each element x in the stack can be the leftmost // element s.t. [x, num] forms a valid subarray, so the stack.size() is // the # of valid subarrays ending at curr num. // // E.g. nums = [1, 3, 2] // num = 1, stack = [1] -> valid subarray is [1] // num = 3, stack = [1, 3] -> valid subarrays are [1, 3], [3] // num = 2, stack = [1, 2] -> valid subarrays are [1, 3, 2], [2] int ans = 0; stack stack; for (const int num : nums) { while (!stack.empty() && stack.top() > num) stack.pop(); stack.push(num); ans += stack.size(); } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public int validSubarrays(int[] nums) { // For each num in nums, each element x in the stack can be the leftmost // element s.t. [x, num] forms a valid subarray, so the stack.size() is // the # of valid subarrays ending at curr num. // // E.g. nums = [1, 3, 2] // num = 1, stack = [1] -> valid subarray is [1] // num = 3, stack = [1, 3] -> valid subarrays are [1, 3], [3] // num = 2, stack = [1, 2] -> valid subarrays are [1, 3, 2], [2] int ans = 0; Deque stack = new ArrayDeque<>(); for (final int num : nums) { while (!stack.isEmpty() && stack.peek() > num) stack.pop(); stack.push(num); ans += stack.size(); } return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution: def validSubarrays(self, nums: List[int]) -> int: # For each num in nums, each element x in the stack can be the leftmost # element s.t. [x, num] forms a valid subarray, so the stack.size() is # the # of valid subarrays ending at curr num. # # E.g. nums = [1, 3, 2] # num = 1, stack = [1] -> valid subarray is [1] # num = 3, stack = [1, 3] -> valid subarrays are [1, 3], [3] # num = 2, stack = [1, 2] -> valid subarrays are [1, 3, 2], [2] ans = 0 stack = [] for num in nums: while stack and stack[-1] > num: stack.pop() stack.append(num) ans += len(stack) return ans