首页 > 试题广场 >

数组单调和

[编程题]数组单调和
  • 热度指数：13460 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

现定义数组单调和为所有元素i的f(i)值之和。这里的f(i)函数定义为元素i左边(不包括其自身)小于等于它的数字之和。请设计一个高效算法，计算数组的单调和。

给定一个数组A同时给定数组的大小n，请返回数组的单调和。保证数组大小小于等于500，同时保证单调和不会超过int范围。

测试样例： 
[1,3,5,2,4,6],6
返回：27
算法知识视频讲解
开通博客
头像 烟花一树终化尘
发表于 2022-04-07 23:50:51
问题转化：求单调和（小和）就是统计该元素前有多少小于等于该数的元素之和。问题和归并两个有序数组求小于等于该数的元素之和一样。所以现在的问题变为统计子问题中单调和。 // 当出现nums[i]<=nums[j]时，统计所有前半段区间内比nums[j]小的数 // 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 tru-th
发表于 2022-07-20 14:45:12
使用小数和的计算原理，用到了二分法。如图所示，使用二分查找的思想，先将p(0,6)（即process(0,6)）压入栈中，然后计算p(0,3)，不断向下压栈，直到left和right相等时返回0，然后进行merge操作，指针p1指向left，p2指向mid+1，两者进行比较，如果p1的值，小于等于p 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 重生之我要当分子
发表于 2025-01-01 14:31:32
解题思路 这是一个数组处理问题，需要计算每个元素左边小于等于它的数字之和。 关键点： 对于每个元素，需要找到其左边所有小于等于它的数 可以使用树状数组优化查询和更新操作 需要离散化数组元素以优化空间使用 算法步骤： 对数组进行离散化处理 使用树状数组维护前缀和 对每个元素，查询小于等于它的数的 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛牛左
发表于 2022-02-16 13:34:38
//从首元素开始，后面大于等于该元素的数量，为总数中该元素需要计算的次数 class MonoSum { public:     int calcMonoSum(vector<int> A, int n) {         / 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划 查找
来自：经典算法题精讲（六）-...
难度：
119条回答 29932浏览

热门推荐

通过挑战的用户

查看代码

相关试题

数组单调和

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号