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 <= A.length <= 50000
0 <= A[i] <= 100000
struct Solution;
impl Solution {
fn valid_subarrays(nums: Vec<i32>) -> i32 {
let mut stack = vec![];
let mut res = 0;
for x in nums {
while let Some(&top) = stack.last() {
if top > x {
stack.pop();
} else {
break;
}
}
stack.push(x);
res += stack.len();
}
res as i32
}
}
#[test]
fn test() {
let nums = vec![1, 4, 2, 5, 3];
let res = 11;
assert_eq!(Solution::valid_subarrays(nums), res);
let nums = vec![3, 2, 1];
let res = 3;
assert_eq!(Solution::valid_subarrays(nums), res);
let nums = vec![2, 2, 2];
let res = 6;
assert_eq!(Solution::valid_subarrays(nums), res);
}