Welcome to Subscribe On Youtube
1063. Number of Valid Subarrays
Description
Given an integer array nums, return the number of non-empty subarrays with the leftmost element of the subarray not larger than other elements in the subarray.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [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: nums = [3,2,1] Output: 3 Explanation: The 3 valid subarrays are: [3],[2],[1].
Example 3:
Input: nums = [2,2,2] Output: 6 Explanation: There are 6 valid subarrays: [2],[2],[2],[2,2],[2,2],[2,2,2].
Constraints:
1 <= nums.length <= 5 * 1040 <= nums[i] <= 105
Solutions
Solution 1: Monotonic Stack
The question is actually to solve the first position $j$ on the right side of each position $i$ that is smaller than $nums[i]$. Then the number of valid subarrays with $i$ as the left endpoint is $j - i$.
We can use a monotonic stack to solve for the first position $j$ on the right that is less than $nums[i]$. The specific method is to traverse the array from right to left and maintain a stack that strictly monotonically decreases from the top to the bottom of the stack. If the stack is not empty, and the top element of the stack is greater than or equal to $nums[i]$, then the top element of the stack is popped until the stack is empty or the top element of the stack is less than $nums[i]$. At this time, the top element of the stack is the first position on the right that is less than $nums[i]$, $j$. If the stack is empty, then $j = n$.
Next, we push $i$ onto the stack and continue to traverse the array until the end of the traversal. Finally, we can get the first position $j$ on the right side of each position $i$ that is smaller than $nums[i]$, thus getting the number of valid subarrays with $i$ as the left endpoint. $j-i$, add up all $j-i$ to get the answer.
The time complexity is $O(n)$, and the space complexity is $O(n)$. where $n$ is the length of the array.
Solution 2
This implementation uses monotonic stack. It traverses the relevant values and updates its state as each value is processed. After all required states have been considered, the maintained result is returned.
-
class Solution { public int validSubarrays(int[] nums) { int n = nums.length; int[] right = new int[n]; Arrays.fill(right, n); Deque<Integer> stk = new ArrayDeque<>(); for (int i = n - 1; i >= 0; --i) { while (!stk.isEmpty() && nums[stk.peek()] >= nums[i]) { stk.pop(); } if (!stk.isEmpty()) { right[i] = stk.peek(); } stk.push(i); } int ans = 0; for (int i = 0; i < n; ++i) { ans += right[i] - i; } return ans; } } // Solution 2 class Solution { public int validSubarrays(int[] nums) { int n = nums.length; Deque<Integer> stk = new ArrayDeque<>(); int ans = 0; for (int i = n - 1; i >= 0; --i) { while (!stk.isEmpty() && nums[stk.peek()] >= nums[i]) { stk.pop(); } ans += (stk.isEmpty() ? n : stk.peek()) - i; stk.push(i); } return ans; } } -
class Solution { public: int validSubarrays(vector<int>& nums) { int n = nums.size(); vector<int> right(n, n); stack<int> stk; for (int i = n - 1; ~i; --i) { while (stk.size() && nums[stk.top()] >= nums[i]) { stk.pop(); } if (stk.size()) { right[i] = stk.top(); } stk.push(i); } int ans = 0; for (int i = 0; i < n; ++i) { ans += right[i] - i; } return ans; } }; // Solution 2 class Solution { public: int validSubarrays(vector<int>& nums) { int n = nums.size(); stack<int> stk; int ans = 0; for (int i = n - 1; ~i; --i) { while (stk.size() && nums[stk.top()] >= nums[i]) { stk.pop(); } ans += (stk.size() ? stk.top() : n) - i; stk.push(i); } return ans; } }; -
class Solution: def validSubarrays(self, nums: List[int]) -> int: n = len(nums) right = [n] * n stk = [] for i in range(n - 1, -1, -1): while stk and nums[stk[-1]] >= nums[i]: stk.pop() if stk: right[i] = stk[-1] stk.append(i) return sum(j - i for i, j in enumerate(right)) # Solution 2 class Solution: def validSubarrays(self, nums: List[int]) -> int: n = len(nums) stk = [] ans = 0 for i in range(n - 1, -1, -1): while stk and nums[stk[-1]] >= nums[i]: stk.pop() ans += (stk[-1] if stk else n) - i stk.append(i) return ans -
func validSubarrays(nums []int) (ans int) { n := len(nums) right := make([]int, n) for i := range right { right[i] = n } stk := []int{} for i := n - 1; i >= 0; i-- { for len(stk) > 0 && nums[stk[len(stk)-1]] >= nums[i] { stk = stk[:len(stk)-1] } if len(stk) > 0 { right[i] = stk[len(stk)-1] } stk = append(stk, i) } for i, j := range right { ans += j - i } return } // Solution 2 func validSubarrays(nums []int) (ans int) { n := len(nums) stk := []int{} for i := n - 1; i >= 0; i-- { for len(stk) > 0 && nums[stk[len(stk)-1]] >= nums[i] { stk = stk[:len(stk)-1] } ans -= i if len(stk) > 0 { ans += stk[len(stk)-1] } else { ans += n } stk = append(stk, i) } return } -
function validSubarrays(nums: number[]): number { const n = nums.length; const right: number[] = Array(n).fill(n); const stk: number[] = []; for (let i = n - 1; ~i; --i) { while (stk.length && nums[stk.at(-1)] >= nums[i]) { stk.pop(); } if (stk.length) { right[i] = stk.at(-1)!; } stk.push(i); } let ans = 0; for (let i = 0; i < n; ++i) { ans += right[i] - i; } return ans; } // Solution 2 function validSubarrays(nums: number[]): number { const n = nums.length; const stk: number[] = []; let ans = 0; for (let i = n - 1; ~i; --i) { while (stk.length && nums[stk.at(-1)!] >= nums[i]) { stk.pop(); } ans += (stk.at(-1) ?? n) - i; stk.push(i); } return ans; }