当前位置: 首页 > news >正文

20240119-子数组最小值之和

题目要求

给定一个整数数组 arr,求 min(b) 的总和,其中 b 的范围涵盖 arr 的每个(连续)子数组。由于答案可能很大,因此返回答案模数10^9+7

Example 1:

Input: arr = [3,1,2,4]
Output: 17
Explanation: 
Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. 
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.
Sum is 17.

Example 2:

Input: arr = [11,81,94,43,3]
Output: 444

思路

找出数组的全部组合数,加和并返回mod(10^9+7)之后的结果。我们只需要找出所有的组合然后加到一起。但是这样至少需要O(N^2)的时间复杂度,会超时。

然后又想到不需要真正求出子数组,只需要求出子数组的最小值即可。同时发现子数组不能交换顺序。因此想到用单调栈解决本题。

  1. 左侧范围:我们需要找出在 arr[i] 左侧的第一个比 arr[i] 小的元素。设这个位置为 L。这意味着从 L+1i 的所有位置,arr[i] 都是最小的。

  2. 右侧范围:类似地,我们找出在 arr[i] 右侧的第一个比 arr[i] 小的元素。设这个位置为 R。这意味着从 iR-1 的所有位置,arr[i] 都是最小的。

知道这两个位置后,我们可以计算以 arr[i] 为最小值的子数组数量。这个数量等于 arr[i] 左侧和右侧可扩展的位置数的乘积。

特别注意:处理数值相同时的情况。只需要在处理左边界或者有边界时候加入一个等号即可。(始终认为出现相同值时,右边的更小)。

代码

class Solution {
public:int sumSubarrayMins(vector<int>& arr) {stack<int> s;int result = 0;int n = arr.size();vector<int> left(n), right(n);long long mod = 1000000007; // 10^9 + 7for (int i = 0; i < n; ++i) {while (!s.empty() && arr[s.top()] >= arr[i]) {right[s.top()] = i;s.pop();}s.push(i);}while (!s.empty()) {right[s.top()] = n;s.pop();}for (int j = n-1; j >= 0; --j) {while (!s.empty() && arr[s.top()] > arr[j]) {left[s.top()] = j;s.pop();}s.push(j);}while (!s.empty()) {left[s.top()] = -1;s.pop();}for (int i = 0; i < n; ++i) {cout << i << " " << left[i] << " " << right[i] << " " << arr[i] << endl;result += ((long long)(i - left[i]) * (right[i] - i) % mod * arr[i] % mod) % mod;result %= mod;}return result;}
};

特别感谢GPT的Code Tutor,这个题目的思路和代码是在它的指导下写出来的,还挺好用的。

时空复杂度

相关文章:

20240119-子数组最小值之和

题目要求 给定一个整数数组 arr&#xff0c;求 min(b) 的总和&#xff0c;其中 b 的范围涵盖 arr 的每个&#xff08;连续&#xff09;子数组。由于答案可能很大&#xff0c;因此返回答案模数 Example 1: Input: arr [3,1,2,4] Output: 17 Explanation: Subarrays are [3]…...

c# 释放所有嵌入资源, 到某个本地文件夹

版本号 .net 8 代码 using System.Reflection;namespace Demo;internal class Program {static void Main(string[] args){// 获取当前 执行exe 的目录 / 当前命令行所在的目录 var currentDir Directory.GetCurrentDirectory();Console.WriteLine(currentDir);Extract…...

Unity SnapScrollRect 滚动 匹配 列表 整页

展示效果 原理: 当停止滑动时 判断Contet的horizontalNormalizedPosition 与子Item的缓存值 相减,并得到最小值&#xff0c;然后将Content horizontalNormalizedPosition滚动过去 使用方式&#xff1a; 直接将脚本挂到ScrollRect上 注意&#xff1a;在创建Content子物体时…...

网络命令ping和telnet

1. 请解释ping和telnet的工作原理。 ping和telnet是两种常用的网络工具&#xff0c;其工作原理分别如下&#xff1a; ping&#xff1a; 目的&#xff1a;ping主要用于检查网络是否通畅以及测量网络连接速度。工作原理&#xff1a;ping是基于ICMP&#xff08;Internet Control …...

ros2学习笔记-CLI工具,记录命令对应操作。

目录 环境变量turtlesim和rqt以初始状态打开rqt node启动节点查看节点列表查看节点更多信息命令行参数 --ros-args topic话题列表话题类型话题列表&#xff0c;附加话题类型根据类型查找话题名查看话题发布的数据查看话题的详细信息查看类型的详细信息给话题发布消息&#xff0…...

自然语言处理的发展

自然语言处理的发展大致经历了四个阶段&#xff1a;萌芽期、快速发展期、低谷的发展期和复苏融合期。 萌芽期&#xff08;1956年以前&#xff09;&#xff1a;这个阶段可以看作自然语言处理的基础研究阶段。人类文明经过了几千年的发展&#xff0c;积累了大量的数学、语言学和…...

flink operator 拉取阿里云私有镜像(其他私有类似)

创建 k8s secret kubectl --namespace flink create secret docker-registry aliyun-docker-registry --docker-serverregistry.cn-shenzhen.aliyuncs.com --docker-usernameops_acr1060896234 --docker-passwordpasswd --docker-emailDOCKER_EMAIL注意命名空间指定你使用的 我…...

C语言算法赛——蓝桥杯(省赛试题)

一、十四届C/C程序设计C组试题 十四届程序C组试题A#include <stdio.h> int main() {long long sum 0;int n 20230408;int i 0;// 累加从1到n的所有整数for (i 1; i < n; i){sum i;}// 输出结果printf("%lld\n", sum);return 0; }//十四届程序C组试题B…...

【文本到上下文 #2】:NLP 的数据预处理步骤

一、说明 欢迎阅读此文&#xff0c;NLP 爱好者&#xff01;当我们继续探索自然语言处理 (NLP) 的广阔前景时&#xff0c;我们已经在最初的博客中探讨了它的历史、应用和挑战。今天&#xff0c;我们更深入地探讨 NLP 的核心——数据预处理的复杂世界。 这篇文章是我们的“完整 N…...

Minio文件分片上传实现

资源准备 MacM1Pro 安装Parallels19.1.0请参考 https://blog.csdn.net/qq_41594280/article/details/135420241 MacM1Pro Parallels安装CentOS7.9请参考 https://blog.csdn.net/qq_41594280/article/details/135420461 部署Minio和整合SpringBoot请参考 https://blog.csdn.net/…...

C语言总结十一:自定义类型:结构体、枚举、联合(共用体)

本篇博客详细介绍C语言最后的三种自定义类型&#xff0c;它们分别有着各自的特点和应用场景&#xff0c;重点在于理解这三种自定义类型的声明方式和使用&#xff0c;以及各自的特点&#xff0c;最后重点掌握该章节常考的考点&#xff0c;如&#xff1a;结构体内存对齐问题&…...

解决Spring Boot应用打包后文件访问问题

在Spring Boot项目的开发过程中&#xff0c;一个常见的挑战是如何有效地访问和操作资源文件。这一挑战尤其显著当应用从IDE环境&#xff08;如IntelliJ IDEA&#xff09;迁移到被打包成JAR文件后的生产环境。开发者经常遇到的问题是&#xff0c;在IDE中运行正常的代码&#xff…...

循环神经网络的变体模型-LSTM、GRU

一.LSTM&#xff08;长短时记忆网络&#xff09; 1.1基本介绍 长短时记忆网络&#xff08;Long Short-Term Memory&#xff0c;LSTM&#xff09;是一种深度学习模型&#xff0c;属于循环神经网络&#xff08;Recurrent Neural Network&#xff0c;RNN&#xff09;的一种变体。…...

视频图像的color range简介

介绍 研究FFmpeg发现&#xff0c;在avcodec.h中有关于color的解释&#xff0c;主要有四个属性&#xff0c;primaries、transfer、space和range。 color primaries&#xff1a; 基于RGB空间对应的绝对颜色XYZ的变换&#xff0c;决定了最终三原色RGB分别是什么颜色&#xff1b;…...

tcp的三次握手

http 和 https 都是是基于 TCP 的请求&#xff0c;https 是 http 加上 tls 连接。TCP 是面向连接的协议。 对于 http1.1 协议chrome 限制在同一个域名下最多可以建立 6 个 tcp 连接&#xff0c;所以如果在同一个域名下&#xff0c;同时有超过 6 个请求发生&#xff0c;那么多余…...

unity 矩阵探究

public void MatrixTest1(){ ///Matrix4x4 是列矩阵&#xff0c;就是一个vector4表示一列&#xff0c;所以在c#中矩阵和Vector4只能矩阵右乘坐标。但是在shader中是矩阵左乘坐标&#xff0c;所以在shader中是行矩阵 Matrix4x4 moveMatrix1 new Matrix4x4(new Vector4(1,0,0,0)…...

MySQL---单表查询综合练习

创建emp表 CREATE TABLE emp( empno INT(4) NOT NULL COMMENT 员工编号, ename VARCHAR(10) COMMENT 员工名字, job VARCHAR(10) COMMENT 职位, mgr INT(4) COMMENT 上司, hiredate DATE COMMENT 入职时间, sal INT(7) COMMENT 基本工资, comm INT(7) COMMENT 补贴, deptno INT…...

Python项目——搞怪小程序(PySide6+Pyinstaller)

1、介绍 使用python编写一个小程序&#xff0c;回答你是猪吗。 点击“是”提交&#xff0c;弹窗并退出。 点击“不是”提交&#xff0c;等待5秒&#xff0c;重新选择。 并且隐藏了关闭按钮。 2、实现 新建一个项目。 2.1、设计UI 使用Qt designer设计一个UI界面&#xff0c…...

MySQL练习题

参考&#xff1a;https://blog.csdn.net/paul0127/article/details/82529216 数据表介绍 --1.学生表 Student(SId,Sname,Sage,Ssex) --SId 学生编号,Sname 学生姓名,Sage 出生年月,Ssex 学生性别 --2.课程表 Course(CId,Cname,TId) --CId 课程编号,Cname 课程名称,TId 教师编号…...

vue-项目打包、配置路由懒加载

1. 简介 在现代前端开发中&#xff0c;Vue.js因其简洁、灵活和高效的特点&#xff0c;已经成为许多开发者的首选框架。 在Vue项目中&#xff0c;打包部署和路由懒加载是两个非常重要的环节。 打包Vue项目是为了将源代码转换为浏览器可以解析的JavaScript文件&#xff0c;以便…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

AxureRP-Pro-Beta-Setup_114413.exe (6.0.0.2887)

Name&#xff1a;3ddown Serial&#xff1a;FiCGEezgdGoYILo8U/2MFyCWj0jZoJc/sziRRj2/ENvtEq7w1RH97k5MWctqVHA 注册用户名&#xff1a;Axure 序列号&#xff1a;8t3Yk/zu4cX601/seX6wBZgYRVj/lkC2PICCdO4sFKCCLx8mcCnccoylVb40lP...

Spring AOP代理对象生成原理

代理对象生成的关键类是【AnnotationAwareAspectJAutoProxyCreator】&#xff0c;这个类继承了【BeanPostProcessor】是一个后置处理器 在bean对象生命周期中初始化时执行【org.springframework.beans.factory.config.BeanPostProcessor#postProcessAfterInitialization】方法时…...

内窥镜检查中基于提示的息肉分割|文献速递-深度学习医疗AI最新文献

Title 题目 Prompt-based polyp segmentation during endoscopy 内窥镜检查中基于提示的息肉分割 01 文献速递介绍 以下是对这段英文内容的中文翻译&#xff1a; ### 胃肠道癌症的发病率呈上升趋势&#xff0c;且有年轻化倾向&#xff08;Bray等人&#xff0c;2018&#x…...