给定一个长度为 n 的数组 nums ,算出他所有的 min(sub) 之和,其中 sub 指数组 nums 的所有连续子数组 , min(sub) 指子数组的最小值。 数据范围: ,数组中的值满足 ,由于结果可能非常大,所以返回结果对 取模的结果

区块链毕设网qklbishe.com为您提供问题的解答

给定一个长度为 n 的数组 nums ,算出他所有的 min(sub) 之和,其中 sub 指数组 nums 的所有连续子数组 , min(sub) 指子数组的最小值。
数据范围: 给定一个长度为 n 的数组 nums ,算出他所有的 min(sub) 之和,其中 sub 指数组 nums 的所有连续子数组 , min(sub) 指子数组的最小值。          数据范围:  ,数组中的值满足  ,由于结果可能非常大,所以返回结果对  取模的结果 ,数组中的值满足 给定一个长度为 n 的数组 nums ,算出他所有的 min(sub) 之和,其中 sub 指数组 nums 的所有连续子数组 , min(sub) 指子数组的最小值。          数据范围:  ,数组中的值满足  ,由于结果可能非常大,所以返回结果对  取模的结果 ,由于结果可能非常大,所以返回结果对 给定一个长度为 n 的数组 nums ,算出他所有的 min(sub) 之和,其中 sub 指数组 nums 的所有连续子数组 , min(sub) 指子数组的最小值。          数据范围:  ,数组中的值满足  ,由于结果可能非常大,所以返回结果对  取模的结果 取模的结果

# -*- coding: utf-8 -*-  # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @return int整型 # class Solution:     """     题目:         https://www.nowcoder.com/practice/a7401d0dd4ec4071a31fd434e150bcc2?tpId=196&tqId=40517&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=     参考:         https://leetcode.cn/problems/sum-of-subarray-minimums/solution/zi-shu-zu-de-zui-xiao-zhi-zhi-he-by-leetcode/     算法:         对于每个 j,考虑所有子序列 [i, j] 的最小值。想法是每当我们增加 j,这些最小值可能会有关联,事实上,min(A[i:j+1]) = min(A[i:j], A[j+1])。         我们维护最小值栈stack,stack中存储的元素为(x, c),表示以x为结尾且x为最小值的区间个数,stack按照x单调递增。枚举区间右端点j,弹出栈中 x >= y的元素,因为这些以x结尾且以x为最小值的区间,尾部追加y之后,变成以y结尾且以y为最小值的区间了。另外我们使用Sum来记录以当前元素y结尾的所有区间的最小值之和。     复杂度:         时间复杂度:O(n)         空间复杂度:O(n)     """      def sumSubarr(self, nums):         # write code here         MOD = 10 ** 9 + 7         ans, Sum, stack = 0, 0, []          for j, y in enumerate(nums):             count = 1             while stack and stack[-1][0] >= y:                 x, c = stack.pop() # 以元素x结尾的区间个数为c,现在我们将元素y作为这些区间的尾部,也就是之前c个以元素x为最小值的区间 变为 以元素y作为最小值的区间                 count += c                 Sum -= x * c # dot始终记录以当前元素y结尾的所有区间的最小值之和             stack.append((y, count)) # count表示以元素y结尾且y作为区间最小值的区间个数             Sum += y * count             ans += Sum # 累加以y结尾的所有区间的最小值之和          return ans % MOD  if __name__ == "__main__":     sol = Solution()      # nums = [3, 1, 2, 4, 5]      # nums = [3, 1, 2, 4]      # nums = [11, 81, 94, 43, 3]      nums = [1, 2]      # nums = [3, 2, 1]      res = sol.sumSubarr(nums)      print res 

30:40

以上就是关于问题给定一个长度为 n 的数组 nums ,算出他所有的 min(sub) 之和,其中 sub 指数组 nums 的所有连续子数组 , min(sub) 指子数组的最小值。
数据范围: ,数组中的值满足 ,由于结果可能非常大,所以返回结果对 取模的结果的答案

欢迎关注区块链毕设网-
专业区块链毕业设计成品源码,定制。

区块链NFT链游项目方科学家脚本开发培训

承接区块链项目定制开发

微信:btc9767

QQ :1330797917

TELEGRAM: BTCOK9

承接区块链项目定制开发


qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台-javagopython毕设 » 给定一个长度为 n 的数组 nums ,算出他所有的 min(sub) 之和,其中 sub 指数组 nums 的所有连续子数组 , min(sub) 指子数组的最小值。 数据范围: ,数组中的值满足 ,由于结果可能非常大,所以返回结果对 取模的结果