[Swift-2019力扣杯春季决赛]4. 有效子数组的数目

概述给定一个整数数组 A，返回满足下面条件的 非空、连续 子数组的数目： 子数组中，最左侧的元素不大于其他元素。 示例 1： 输入：[1,4,2,5,3]输出：11解释：有 11 个有效子数组，分别是：[1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3] 。 示例 2： 输入：[3,2,1]输出：3

给定一个整数数组 A，返回满足下面条件的 非空、连续 子数组的数目：

子数组中，最左侧的元素不大于其他元素。

示例 1：

输入：[1,4,2,5,3]输出：11解释：有 11 个有效子数组，分别是：[1],[4],[2],[5],[3],[1,4],[2,5],2],3],3] 。

示例 2：

输入：[3,1]输出：3解释：有 3 个有效子数组，分别是：[3],[1] 。

示例 3：

输入：[2,2]输出：6解释：有 6 个有效子数组，分别为是：[2],2] 。

提示：

1 <= A.length <= 50000 0 <= A[i] <= 100000

848 ms

 1 class Solution { 2     var ne:[Int] = [Int](repeating:0,count:50005) 3     var st:[Int] = [Int](repeating:0,count:50005) 4     var t:Int = 0 5     func valIDSubarrays(_ nums: [Int]) -> Int { 6         var n:Int = nums.count 7         var ans:Int = 0 8         st[0] = n 9         for i in strIDe(from:(n - 1),through:0,by:-1)10         {11             while((t != 0) && nums[st[t]] >= nums[i])12             {13                 t -= 114             }15             ne[i] = st[t]16             t += 117             st[t] = i18             ans += ne[i] - i19         }20         return ans21     }22 }

总结

以上是内存溢出为你收集整理的[Swift-2019力扣杯春季决赛]4. 有效子数组的数目全部内容，希望文章能够帮你解决[Swift-2019力扣杯春季决赛]4. 有效子数组的数目所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。