首页 > 试题广场 >

子数组的最小值之和

[编程题]子数组的最小值之和
  • 热度指数：746 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个长度为 n 的数组 nums ，算出他所有的 min(sub) 之和，其中 sub 指数组 nums 的所有连续子数组 ， min(sub) 指子数组的最小值。

数据范围： ，数组中的值满足 ，由于结果可能非常大，所以返回结果对 取模的结果
示例1

输入

[3,1,2,4,5]

输出

30

说明

子数组有 3、1、2、4、5、（3，1）、（3，2）、（3，4）、（3，5）、（1，2）、（1，4）、（1，5）、（2，4）、（2，5）、（4，5）、（3，1，2）、（3，1，4）、（3，1，5）、（3，2，4）、（3，4，5）、（1，2，4）、（1，2，5）、（2，4，5）、（3，1，2，4）、（3，1，2，5）、（3，2，4，5）、（1，2，4，5） 其最小值和是 30
算法知识视频讲解
开通博客
头像 太阳hxy
发表于 2023-09-03 10:30:35
思路： class Solution { public: int sumSubarr(vector<int>& nums) { int n=nums.size(); long ans=0; //leftmin用于存每个元素 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 DrinkingLyu
发表于 2024-07-11 17:34:27
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @r 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 觉醒火龙果很想五点下课
发表于 2025-05-17 18:26:54
class Solution { public: //对于数组中的一个数，看他的左边有多少大于他的数，右边有多少大于它的数，两个值相乘，即以本值为最小值的连续子树组的个数， //要找到最近的小于它的数，使用栈，递增栈，保留的是局部最小值，只用比较局部最小值即可；数组记录全局最小值； 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 17c89
发表于 2024-07-30 14:20:23
import java.util.*; import java.util.stream.IntStream; /** * NC386 子数组的最小值之和 * @author d3y1 */ public class Solution { private final int MOD = 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划 栈 单调栈
难度：
4条回答 3765浏览

热门推荐

通过挑战的用户

查看代码

相关试题

子数组的最小值之和

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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