【C++单调栈 贡献法】907. 子数组的最小值之和|1975
本文涉及的基础知识点
C++单调栈
LeetCode907. 子数组的最小值之和
给定一个整数数组 arr,找到 min(b) 的总和,其中 b 的范围为 arr 的每个(连续)子数组。
由于答案可能很大,因此 返回答案模 109 + 7 。
示例 1:
输入:arr = [3,1,2,4]
输出:17
解释:
子数组为 [3],[1],[2],[4],[3,1],[1,2],[2,4],[3,1,2],[1,2,4],[3,1,2,4]。
最小值为 3,1,2,4,1,1,2,1,1,1,和为 17。
示例 2:
输入:arr = [11,81,94,43,3]
输出:444
提示:
1 <= arr.length <= 3 * 104
1 <= arr[i] <= 3 * 104
单调栈
枚举子数组的最小元素a[i],令a[i1…i2]包括a[i],且a[i]是其的最小元素,即 i1 <=x < i ,则a[x]大于a[i];i < x <=i2,则a[x] >=a[i]。
令最小i1是i3,最大i2是i4。则a[i]是其最小元素的子数组数量为:f(i)=(i-i3+1) × \times ×(i4-i+1)。结果是:
∑ \sum ∑f(i)
如何求a[0…i-1]中小于等于a[i]的元素中下标最大的?
i5 < i6,且a[i5] > a[i6],则i5 永远不会被选中。即i5被i6淘汰了。淘汰后,值升序。淘汰后,栈顶元素(小于等于a[i]的最大下标)+1,就是i3,如果是空栈则为-1。
i5被i6淘汰说明,说明i6是a[i6] < a[i5]中下标最小的。即i6就是i5的i4+1.如果i5没被淘汰,则i4+1是n。
代码
核心代码
template<int MOD = 1000000007>
class C1097Int
{
public:C1097Int(long long llData = 0) :m_iData(llData% MOD){}C1097Int operator+(const C1097Int& o)const{return C1097Int(((long long)m_iData + o.m_iData) % MOD);}C1097Int& operator+=(const C1097Int& o){m_iData = ((long long)m_iData + o.m_iData) % MOD;return *this;}C1097Int& operator-=(const C1097Int& o){m_iData = (m_iData + MOD - o.m_iData) % MOD;return *this;}C1097Int operator-(const C1097Int& o){return C1097Int((m_iData + MOD - o.m_iData) % MOD);}C1097Int operator*(const C1097Int& o)const{return((long long)m_iData * o.m_iData) % MOD;}C1097Int& operator*=(const C1097Int& o){m_iData = ((long long)m_iData * o.m_iData) % MOD;return *this;}C1097Int operator/(const C1097Int& o)const{return *this * o.PowNegative1();}C1097Int& operator/=(const C1097Int& o){*this /= o.PowNegative1();return *this;}bool operator==(const C1097Int& o)const{return m_iData == o.m_iData;}bool operator<(const C1097Int& o)const{return m_iData < o.m_iData;}C1097Int pow(long long n)const{C1097Int iRet = 1, iCur = *this;while (n){if (n & 1){iRet *= iCur;}iCur *= iCur;n >>= 1;}return iRet;}C1097Int PowNegative1()const{return pow(MOD - 2);}int ToInt()const{return m_iData;}
private:int m_iData = 0;;
};class Solution {public:int sumSubarrayMins(vector<int>& arr) {const int N = arr.size(); stack<int> sta;vector<int> i3s(N, -1), i4s(N, N);for (int i = 0; i < arr.size(); i++) {while (sta.size() && (arr[sta.top()] > arr[i])) {i4s[sta.top()] = i;sta.pop(); }if (sta.size()) { i3s[i] = sta.top(); }sta.emplace(i);}C1097Int<> res;for (int i = 0; i < N; i++) {res += C1097Int<>(i-i3s[i]) *( i4s[i]-i)*arr[i];}return res.ToInt();}};
单元测试
vector<int> arr;TEST_METHOD(TestMethod1){arr = { 3 };auto res = Solution().sumSubarrayMins(arr);AssertEx(3, res);}TEST_METHOD(TestMethod2){arr = { 3,3 };auto res = Solution().sumSubarrayMins(arr);AssertEx(9, res);}TEST_METHOD(TestMethod3){arr = { 3,1 };auto res = Solution().sumSubarrayMins(arr);AssertEx(5, res);}TEST_METHOD(TestMethod11){arr = { 3,1,2,4 };auto res = Solution().sumSubarrayMins(arr);AssertEx(17, res);}TEST_METHOD(TestMethod12){arr = { 11,81,94,43,3 };auto res = Solution().sumSubarrayMins(arr);AssertEx(444, res);}

扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。 |
| 学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作 |
| 有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
| 子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙,那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

相关文章:
【C++单调栈 贡献法】907. 子数组的最小值之和|1975
本文涉及的基础知识点 C单调栈 LeetCode907. 子数组的最小值之和 给定一个整数数组 arr,找到 min(b) 的总和,其中 b 的范围为 arr 的每个(连续)子数组。 由于答案可能很大,因此 返回答案模 109 7 。 示例 1&#x…...
极狐GitLab 17.5 发布 20+ 与 DevSecOps 相关的功能【二】
GitLab 是一个全球知名的一体化 DevOps 平台,很多人都通过私有化部署 GitLab 来进行源代码托管。极狐GitLab 是 GitLab 在中国的发行版,专门为中国程序员服务。可以一键式部署极狐GitLab。 学习极狐GitLab 的相关资料: 极狐GitLab 官网极狐…...
Django 5 增删改查 小练习
1. 用命令创建目录和框架 django-admin startproject myapp cd myapp py manage.py startapp app md templates md static md media 2. Ai 生成代码 一、app/models.py from django.db import modelsclass Product(models.Model):name models.CharField(max_length255, verb…...
【STM32 Blue Pill编程实例】-I2C主从机通信(中断、DMA)
I2C主从机通信(中断、DMA) 文章目录 I2C主从机通信(中断、DMA)1、STM32的I2C介绍2、I2C模式3、STM32 I2C 数据包错误检查4、STM32 I2C 错误情况5、STM32 I2C中断6、STM32 I2C 主发送和接收(Tx 和 RX)6.1 I2C 轮询模式6.2 I2C 中断模式6.3 I2C DMA 模式6.4 STM32 I2C 设备…...
基于SSM+小程序的旅游社交登录管理系统(旅游4)
👉文末查看项目功能视频演示获取源码sql脚本视频导入教程视频 1、项目介绍 本旅游社交小程序功能有管理员和用户。管理员有个人中心,用户管理,每日签到管理,景点推荐管理,景点分类管理,防疫查询管理&a…...
高级java每日一道面试题-2024年10月24日-JVM篇-说一下JVM有哪些垃圾回收器?
如果有遗漏,评论区告诉我进行补充 面试官: 说一下JVM有哪些垃圾回收器? 我回答: 1. Serial收集器 特点:Serial收集器是最古老、最稳定的收集器,它使用单个线程进行垃圾收集工作。在进行垃圾回收时,它会暂停所有用户线程,即St…...
Java-内部类
个人主页 学习内部类(Inner Class)是Java编程中一项重要且强大的特性,它允许你在一个类的内部定义另一个类。内部类提供了一种将逻辑上相关的类组织在一起的方式,增加了代码的封装性和可读性。接下来带领大家进入內部类的学习。 …...
flutter集成极光推送
一、简述 极光推送,英文简称 JPush,免费的第三方消息推送服务,官方也推出众多平台的SDK以及插件。 参考链接 名称地址客户端集成插件客户端集成插件 - 极光文档 二、操作步骤 2.1 添加插件 flutter项目中集成官方提供的 极光推送flutte…...
D. Skipping 【 Codeforces Round 980 (Div. 2)】
D. Skipping 思路: 注意到最佳策略是先往右跳转到某处,然后按顺序从右往左把没有遇到过的题目全部提交。 将从 i i i跳转到 b [ i ] b[i] b[i]视为通过边权(代价)为 a [ i ] a[i] a[i]的路径,而向左的路径边权都是 0 0 0;目的是找到到从出发…...
【golang】学习文档整理
Binding | Echo 传值时注意零值和传空的区别 需要validate require 和 设置指针配合使用 保证不同值的返回不同 不能客户端传0值被判断为空 测试时要空值零值去测试字段是否正确返回 返回错误是否符合预期...
动态规划-子序列问题——1218.最长定差子序列
1.题目解析 题目来源:1218.最长定差子序列——力扣 测试用例 2.算法原理 1.状态表示 本题可以看作是寻找一个等差序列,并且公差给出,这里并不是普通的使用一个dp表,而是将arr与dp表同时存储于一个哈希表,arr[i]映射dp…...
双子塔楼宇可视化系统:提升建筑管理与运营效率
利用图扑可视化技术对双子塔楼宇的各项功能进行实时监控和管理。通过数据分析优化资源配置,提高能源效率,增强楼宇安全性,实现智能化运营。...
32位的ARMlinux的4字节变量原子访问问题
在32位的ARM Linux内核中,4字节整型变量通常被认为是原子操作。 这主要是因为: 对齐要求:在ARM架构中,4字节整型变量通常是按4字节对齐存储的,这样可以确保在读取和写入时,CPU能够以单个指令完成操作。 …...
用哪种建站程序做谷歌SEO更容易?
做网站很容易,但做一个能带来流量和订单的网站就没那么简单了。尤其是在谷歌SEO优化方面,不同的建站程序对SEO的支持程度也不同。在这方面,WordPress和Shopify无疑是最佳选择。 WordPress作为一个内容管理系统(CMS)&am…...
IPsec简单介绍
VPN相关介绍 VPN:虚拟私有网络 例如:像这种不加密的 PPTPL2TP ------- 一般用在windows server 服务端(但是大多数企业不用这个) 假如总公司内部的PC1要去访问分公司内部的PC2(一般用在公司服务器有内网的服务&#…...
颠覆级AI:10秒生成超清视频
颠覆级AI:10秒生成超清视频 Pyramid-Flow 是一款开源 AI 视频生成神器💻,只需文字或图片即可极速生成高清视频🎥!高效、高清、资源需求低,适合创作广告、教学视频等多种用途🚀,快来…...
《西安科技大学学报》
《西安科技大学学报》主要刊载安全科学与工程、矿业工程、建筑与土木工程、地质与环境工程、测绘工程、材料科学与工程、化学与化工、机械工程、电气工程及自动化、通信与信息工程、计算机科学与工程、矿业经济管理等专业领域内具有创新性的学术论文和科研成果。 来稿必须符合以…...
redis详细教程(2.List教程)
List是一种可以存储多个有序字符串的数据类型,其中的元素按照顺序排列(可以重复出现),可以通过数字索引来访问列表中的元素,索引可以从左到右或者从右到左。 Redis 列表可以通过两种方式实现:压缩列表&…...
电子电气架构 --- 电气系统工程
我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 屏蔽力是信息过载时代一个人的特殊竞争力,任何消耗你的人和事,多看一眼都是你的不对。非必要不费力证明自己,无利益不试图说服别人,是精神上的节…...
15-4连续子串和的整除问题
问题描述 小M是一个五年级的小学生,今天他学习了整除的知识,想通过一些练习来巩固自己的理解。他写下了一个长度为 n 的正整数序列 a_0, a_1, ..., a_{n-1},然后想知道有多少个连续子序列的和能够被一个给定的正整数 b 整除。你能帮小M解决这…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
C/C++ 中附加包含目录、附加库目录与附加依赖项详解
在 C/C 编程的编译和链接过程中,附加包含目录、附加库目录和附加依赖项是三个至关重要的设置,它们相互配合,确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中,这些概念容易让人混淆,但深入理解它们的作用和联…...
nnUNet V2修改网络——暴力替换网络为UNet++
更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...
【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅
目录 前言 操作系统与驱动程序 是什么,为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中,我们在使用电子设备时,我们所输入执行的每一条指令最终大多都会作用到硬件上,比如下载一款软件最终会下载到硬盘上&am…...
【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅!
【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅! 🌱 前言:一棵树的浪漫,从数组开始说起 程序员的世界里,数组是最常见的基本结构之一,几乎每种语言、每种算法都少不了它。可你有没有想过,一组看似“线性排列”的有序数组,竟然可以**“长”成一棵平衡的二…...
