LeetCode: Number of Valid Subarrays Posted on August 25, 2019July 26, 2020 by braindenny Number of Valid Subarrays Similar Problems: CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #monotone 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 Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. Solution: // https://code.dennyzhang.com/number-of-valid-subarrays // Basic Ideas: Monotone stack // Find the next bigger value for a given element // Complexity: Time O(n), Space O(n) func validSubarrays(nums []int) int { l := make([]int, len(nums)) for i, _ := range l { l[i] = len(nums) } stack := []int{} for i, v := range nums { for len(stack) > 0 && nums[stack[len(stack)-1]] > v { l[stack[len(stack)-1]] = i stack = stack[0:len(stack)-1] } stack = append(stack, i) } res := 0 for i, _ := range nums { res += l[i]-i } return res } Post Views: 0