number-of-valid-subarrays

< Previous 　　　　　　　　　　　　　　　　 Next >

1063. Number of Valid Subarrays (Hard)

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

Related Topics

[Stack] [Array] [Monotonic Stack]

Hints

Hint 1

Given a data structure that answers queries of the type to find the minimum in a range of an array (Range minimum query (RMQ) sparse table) in O(1) time. How can you solve this problem?

Hint 2

For each starting index do a binary search with an RMQ to find the ending possible position.