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
PythonJavaC++GoTypeScript
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))(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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;
}(code-box)
Solution 2
PythonJavaC++GoTypeScript
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(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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;
}(code-box)
