【前缀和】【单调栈】LeetCode2281:巫师的总力量和

作者推荐

map|动态规划|单调栈|LeetCode975:奇偶跳

涉及知识点

单调栈
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频

题目

作为国王的统治者，你有一支巫师军队听你指挥。
给你一个下标从 0 开始的整数数组 strength ，其中 strength[i] 表示第 i 位巫师的力量值。对于连续的一组巫师（也就是这些巫师的力量值是 strength 的 子数组），总力量 定义为以下两个值的 乘积 ：
巫师中 最弱 的能力值。
组中所有巫师的个人力量值 之和 。
请你返回 所有 巫师组的 总 力量之和。由于答案可能很大，请将答案对 109 + 7 取余 后返回。
子数组 是一个数组里 非空 连续子序列。
示例 1：
输入：strength = [1,3,1,2]
输出：44
解释：以下是所有连续巫师组：

  • [1,3,1,2] 中 [1] ，总力量值为 min([1]) * sum([1]) = 1 * 1 = 1
  • [1,3,1,2] 中 [3] ，总力量值为 min([3]) * sum([3]) = 3 * 3 = 9
  • [1,3,1,2] 中 [1] ，总力量值为 min([1]) * sum([1]) = 1 * 1 = 1
  • [1,3,1,2] 中 [2] ，总力量值为 min([2]) * sum([2]) = 2 * 2 = 4
  • [1,3,1,2] 中 [1,3] ，总力量值为 min([1,3]) * sum([1,3]) = 1 * 4 = 4
  • [1,3,1,2] 中 [3,1] ，总力量值为 min([3,1]) * sum([3,1]) = 1 * 4 = 4
  • [1,3,1,2] 中 [1,2] ，总力量值为 min([1,2]) * sum([1,2]) = 1 * 3 = 3
  • [1,3,1,2] 中 [1,3,1] ，总力量值为 min([1,3,1]) * sum([1,3,1]) = 1 * 5 = 5
  • [1,3,1,2] 中 [3,1,2] ，总力量值为 min([3,1,2]) * sum([3,1,2]) = 1 * 6 = 6
  • [1,3,1,2] 中 [1,3,1,2] ，总力量值为 min([1,3,1,2]) * sum([1,3,1,2]) = 1 * 7 = 7
    所有力量值之和为 1 + 9 + 1 + 4 + 4 + 4 + 3 + 5 + 6 + 7 = 44 。
    示例 2：

输入：strength = [5,4,6]
输出：213
解释：以下是所有连续巫师组：

  • [5,4,6] 中 [5] ，总力量值为 min([5]) * sum([5]) = 5 * 5 = 25
  • [5,4,6] 中 [4] ，总力量值为 min([4]) * sum([4]) = 4 * 4 = 16
  • [5,4,6] 中 [6] ，总力量值为 min([6]) * sum([6]) = 6 * 6 = 36
  • [5,4,6] 中 [5,4] ，总力量值为 min([5,4]) * sum([5,4]) = 4 * 9 = 36
  • [5,4,6] 中 [4,6] ，总力量值为 min([4,6]) * sum([4,6]) = 4 * 10 = 40
  • [5,4,6] 中 [5,4,6] ，总力量值为 min([5,4,6]) * sum([5,4,6]) = 4 * 15 = 60
    所有力量值之和为 25 + 16 + 36 + 36 + 40 + 60 = 213 。
    参数范围：
    1 <= strength.length <= 105
    1 <= strength[i] <= 109

单调栈+两个前缀和

时间复杂度: O(n)。

单调栈

枚举各数组的最小值。left 是从右向左第一个小于strength[i]的下标是left，如果不存在left是-1;right是从左向右第一个小于等于strength[i]的下标，如果不存在right为m_c。
如果一个子数组strength[li,ri]的最小值是strength[i]，且strength[i]左边没有和它相等的值。则：
li的取值范围是：(left,i]
ri的取值范围是：[i,right)
我们可以这样计算这些子数组和的和。累加strength[i]它出现的次数。
无论li和ri取值什么，i都在子数组中，所以i出现：(i-left)(right-i)次。
li为left+1时,ri无论取值什么，都包括strength[left+1]
li为left+1和left+2时，ri无论取值什么，都包括strength[left+2]
…

(left,i)中的元素分别出现:right-i次、(right-i)*2、(right-i)*3…

(i,right)中的元素，分别出现：…、(i-left)*2、(i-left)次

前缀和

vPreSum[i] 记录：strength[j]的和，j取值范围[0,i)。
vPreSum2[i]记录：strength[j]*(j+1)的和，j取值范围[0,i)。

代码

核心代码

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;}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 CRangIndex
{
public:template<class _Pr>CRangIndex(const vector<int>& nums, _Pr CurIndexCmpStackTopIndex){m_c = nums.size();m_vLeft.assign(m_c, -1);m_vRight.assign(m_c, m_c);stack<int> sta;for (int i = 0; i < m_c; i++){while (sta.size() && (CurIndexCmpStackTopIndex(i, sta.top()))){m_vRight[sta.top()] = i;sta.pop();}if (sta.size()){m_vLeft[i] = sta.top();}sta.emplace(i);}}int m_c;vector<int> m_vLeft, m_vRight;//vLeft[i] 从右向左第一个小于nums[i] ;vRight[i] 是第一个小于等于nums[i]。
};template<class T = long long >
vector<T> CreatePreSum(const vector<int>& nums)
{vector<T> preSum;preSum.push_back(0);for (int i = 0; i < nums.size(); i++){preSum.push_back (preSum[i]+ nums[i]);}return preSum;
}class Solution {
public:int totalStrength(vector<int>& strength) {CRangIndex ri(strength, [&](int i1, int i2) {return strength[i1] <= strength[i2]; });auto vPreSum = CreatePreSum<C1097Int<>>(strength);vector<C1097Int<>> vPreSum2 = { 0 };for (int i = 0 ; i < ri.m_c ;  i++ ){const auto& n = strength[i];vPreSum2.emplace_back(vPreSum2.back() + C1097Int<>(n)*(i+1));}C1097Int<> biRet = 0;for (int i = 0; i < ri.m_c; i++){const int left = ri.m_vLeft[i];const int right = ri.m_vRight[i];const int leftLen = i - left;//左边界的可选范围(left,i]const int rightLen = right - i;//右边界的可选范围[i,right)//计算(left,i)的巫师和C1097Int<> leftTotal = vPreSum2[i] - vPreSum2[left + 1] - (vPreSum[i] - vPreSum[left + 1]) * (left+1);//计算(i,right)的巫师和C1097Int<> rightTotal = (vPreSum[right] - vPreSum[i + 1])*(right+1) - ( vPreSum2[right] - vPreSum2[i + 1] );C1097Int<> iTotal = C1097Int<>(strength[i]) * leftLen * rightLen;//计算以小标i为最弱力量的子数组C1097Int<> cur = leftTotal * rightLen + rightTotal * leftLen + iTotal;cur *= strength[i];biRet += cur;}return biRet.ToInt();}
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){Assert(v1[i], v2[i]);}
}int main()
{vector<int> strength;{Solution slu;strength = { 2,3,4 };auto res = slu.totalStrength(strength);Assert(78, res);}{Solution slu;strength = { 1 };auto res = slu.totalStrength(strength);Assert(1, res);}{Solution slu;strength = { 1,3 };auto res = slu.totalStrength(strength);Assert(14, res);}{Solution slu;strength = { 1, 3, 1, 2 };auto res = slu.totalStrength(strength);Assert(44, res);}{Solution slu;strength = { 5,4,6 };auto res = slu.totalStrength(strength);Assert(213, res);}{Solution slu;strength.assign(100'000, 1000'000'000);auto res = slu.totalStrength(strength);Assert(611131623, res);}//CConsole::Out(res);
}

2023年3月版

class Solution {
public:
int totalStrength(vector& strength) {
m_c = strength.size();
vector vSum1(1), vSum2(1);
for (int i = 0; i < m_c; i++)
{
vSum1.push_back(vSum1.back() + strength[i]);
vSum2.push_back(vSum2.back() + (long long)strength[i] * (i + 1));
}
vector vLeft(m_c), vRight(m_c);
{
std::vector<std::pair<int, int>> vValueIndex;
for (int i = 0; i < m_c; i++)
{
const int iLessEqualNum = std::lower_bound(vValueIndex.begin(), vValueIndex.end(), strength[i] + 1, LessPairInt) - vValueIndex.begin();
vLeft[i] = (0 == iLessEqualNum) ? -1 : vValueIndex[iLessEqualNum - 1].second;
while (vValueIndex.size() && (vValueIndex.back().first >= strength[i]))
{
vValueIndex.pop_back();
}
vValueIndex.emplace_back(strength[i], i);
}
}
{
std::vector<std::pair<int, int>> vValueIndex;
for (int i = m_c - 1; i >= 0; i–)
{
const int iLessNum = std::lower_bound(vValueIndex.begin(), vValueIndex.end(), strength[i], LessPairInt) - vValueIndex.begin();
vRight[i] = (0 == iLessNum) ? m_c : vValueIndex[iLessNum - 1].second;
while (vValueIndex.size() && (vValueIndex.back().first >= strength[i]))
{
vValueIndex.pop_back();
}
vValueIndex.emplace_back(strength[i], i);
}
}

	 C1097Int llSum = 0;for (int i = 0; i < m_c; i++){const int iLeftLeft = vLeft[i] + 1;const int iLeftRight = i - 1;const int iRightLeft = i + 1;const int iRightRight = vRight[i] - 1;const int iLeftLen = iLeftRight - iLeftLeft + 1;const int iRightLen = iRightRight - iRightLeft + 1;C1097Int llCurSun = ((long long)iLeftLen + 1)*(iRightLen + 1)*strength[i];C1097Int llLeftSum = 0, llRightSum = 0;if (iLeftLen > 0){llLeftSum = vSum2[iLeftRight + 1] - vSum2[iLeftLeft] - (vSum1[iLeftRight + 1] - vSum1[iLeftLeft])*iLeftLeft;llLeftSum *= (iRightLen + 1);}if (iRightLen > 0){llRightSum = (vSum1[iRightRight + 1] - vSum1[iRightLeft])*(iRightRight + 2) - (vSum2[iRightRight + 1] - vSum2[iRightLeft]);llRightSum *= (iLeftLen + 1);}llCurSun += llLeftSum;llCurSun += llRightSum;llSum += llCurSun*strength[i];}return llSum.ToInt();}int m_c;

};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用C++ 实现。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/222398.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【Matlab in VSCode】在VSCode中编辑MATLAB文件

【Matlab in VSCode】在VSCode中编辑MATLAB文件

【Matlab in VSCode】在VSCode中编辑MATLAB文件 1.安装插件 插件&#xff1a;在vscode拓展商店下载 MATLABMatlab in VSCode 其他&#xff1a;Windows环境MATLAB2019bpython3.7.9 2.插件配置 MATLAB插件下载后不用配置。 Matlab in VSCode需要进行相应的配置。 Windows…
阅读更多...
【C语言】自定义类型：结构体深入解析（二）结构体内存对齐宏offsetof计算偏移量结构体传参

【C语言】自定义类型：结构体深入解析（二）结构体内存对齐宏offsetof计算偏移量结构体传参

文章目录 &#x1f4dd;前言&#x1f320; 结构体内存对齐&#x1f309;内存对齐包含结构体的计算&#x1f320;宏offsetof计算偏移量&#x1f309;为什么存在内存对⻬?&#x1f320; 结构体传参&#x1f6a9;总结 &#x1f4dd;前言 本小节&#xff0c;我们学习结构的内存对…
阅读更多...
C++面向对象（OOP）编程-STL详解（vector）

C++面向对象（OOP）编程-STL详解（vector）

本文主要介绍STL六大组件&#xff0c;并主要介绍一些容器的使用。 目录 1 泛型编程 2 CSTL 3 STL 六大组件 4 容器 4.1 顺序性容器 4.1.1 顺序性容器的使用场景 4.2 关联式容器 4.2.1 关联式容器的使用场景 4.3 容器适配器 4.3.1 容器适配器的使用场景 5 具体容器的…
阅读更多...
大模型ChatGLM下载、安装与使用

大模型ChatGLM下载、安装与使用

在人工智能领域&#xff0c;清华技术成果转化的公司智谱AI启动了支持中英双语的对话机器人ChatGLM内测。ChatGLM是一个初具问答和对话功能的千亿中英语言模型&#xff0c; 并针对中文进行了优化&#xff0c;现已开启邀请制内测&#xff0c;后续还会逐步扩大内测范围。 ChatGLM…
阅读更多...
Unity中Shader平移矩阵

Unity中Shader平移矩阵

文章目录 前言方式一&#xff1a;对顶点本地空间下的坐标进行相加平移1、在属性面板定义一个四维变量记录在 xyz 上平移多少。2、在常量缓冲区进行申明3、在顶点着色器中&#xff0c;在进行其他坐标转化之前&#xff0c;对模型顶点本地空间下的坐标进行转化4、我们来看看效果 方…
阅读更多...
Tomcat报404问题解决方案大全(包括tomcat可以正常运行但是报404)

Tomcat报404问题解决方案大全(包括tomcat可以正常运行但是报404)

文章目录 Tomcat报404问题解决方案大全(包括tomcat可以正常运行但是报404)1、正确的运行页面2、报错404问题分类解决2.1、Tomcat未配置环境变量2.2、IIs访问权限问题2.3、端口占用问题2.4、文件缺少问题解决办法&#xff1a; Tomcat报404问题解决方案大全(包括tomcat可以正常运…
阅读更多...
智能优化算法应用：基于龙格-库塔算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用：基于龙格-库塔算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于龙格-库塔算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于龙格-库塔算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.龙格-库塔算法4.实验参数设定5.算法结果…
阅读更多...
@vue/cli脚手架

@vue/cli脚手架

0_vue/cli 脚手架介绍 目标: webpack自己配置环境很麻烦, 下载vue/cli包,用vue命令创建脚手架项目 vue/cli是Vue官方提供的一个全局模块包(得到vue命令), 此包用于创建脚手架项目 脚手架是为了保证各施工过程顺利进行而搭设的工作平 vue/cli的好处 开箱即用 0配置webpack babe…
阅读更多...
算法模板之栈图文详解

算法模板之栈图文详解

&#x1f308;个人主页&#xff1a;聆风吟 &#x1f525;系列专栏&#xff1a;算法模板、数据结构 &#x1f516;少年有梦不应止于心动&#xff0c;更要付诸行动。 文章目录 &#x1f4cb;前言一. ⛳️模拟栈1.1 &#x1f514;用数组模拟实现栈1.1.1 &#x1f47b;栈的定义1.1.…
阅读更多...
SQL---Zeppeline前驱记录与后驱记录查询

SQL---Zeppeline前驱记录与后驱记录查询

内容导航 类别内容导航机器学习机器学习算法应用场景与评价指标机器学习算法—分类机器学习算法—回归机器学习算法—聚类机器学习算法—异常检测机器学习算法—时间序列数据可视化数据可视化—折线图数据可视化—箱线图数据可视化—柱状图数据可视化—饼图、环形图、雷达图统…
阅读更多...
JMeter常见配置及常见问题修改

JMeter常见配置及常见问题修改

一、设置JMeter默认打开字体 1、进入安装目录&#xff1a;apache-jmeter-x.x.x\bin\ 2、找到 jmeter.properties&#xff0c;打开。 3、搜索“ languageen ”&#xff0c;前面带有“#”号.。 4、去除“#”号&#xff0c;并修改为&#xff1a;languagezh_CN 或 直接新增一行&…
阅读更多...
Zookeeper集群搭建，四字命令监控，Leader选举原理以及数据如何同步

Zookeeper集群搭建，四字命令监控，Leader选举原理以及数据如何同步

Java学习面试指南&#xff1a;https://javaxiaobear.cn 1、集群角色 Leader&#xff1a; 领导者。 事务请求&#xff08;写操作&#xff09;的唯一调度者和处理者&#xff0c;保证集群事务处理的顺序性&#xff1b;集群内部各个服务器的调度者。对于create、setData、delete…
阅读更多...
汽车制造厂设备故障预测与健康管理PHM

汽车制造厂设备故障预测与健康管理PHM

在现代汽车制造工业中&#xff0c;设备的可靠性和稳定性对于保证生产线的高效运行至关重要。为了提高生产效率、降低维修成本以及确保产品质量&#xff0c;汽车制造厂逐渐采用设备故障预测与健康管理&#xff08;PHM&#xff09;系统&#xff0c;以实现对设备状态的实时监测和预…
阅读更多...
[数据结构进阶 C++] 二叉搜索树(BinarySearchTree)的模拟实现

[数据结构进阶 C++] 二叉搜索树(BinarySearchTree)的模拟实现

文章目录 1、二叉搜索树1.1 二叉搜索数的概念1.2 二叉搜索树的操作1.2.1 二叉搜索树的查找1.2.2 二叉搜索树的插入1.2.3 二叉搜索树的删除 2、二叉搜索树的应用2.1 K模型2.2 KV模型 3、二叉搜索树的性能分析4、K模型与KV模型完整代码4.1 二叉搜索树的模拟实现&#xff08;K模型…
阅读更多...
【Java】编写一个简单的Servlet程序

【Java】编写一个简单的Servlet程序

Java Servlet 是运行在 Web 服务器或应用服务器上的程序&#xff0c;它是作为来自 Web 浏览器或其他 HTTP 客户端的请求和 HTTP 服务器上的数据库或应用程序之间的中间层。 使用 Servlet&#xff0c;可以收集来自网页表单的用户输入&#xff0c;呈现来自数据库或者其他源的记录…
阅读更多...
求交错序列前N项和 C语言xdoj149

求交错序列前N项和 C语言xdoj149

题目描述&#xff1a;编写程序&#xff0c;计算交错序列1-2/33/5-4/75/9-6/11…的前N项之和。 输入格式&#xff1a;输入一个正整数 输出格式&#xff1a;输出计算结果&#xff0c;结果保留三位小数 示例&#xff1a; 输入&#xff1a;5 输出&#xff1a;0.917 #include <st…
阅读更多...
基于深度学习的森林火焰烟雾检测系统（含UI界面，yolov8、Python代码，数据集）

基于深度学习的森林火焰烟雾检测系统（含UI界面，yolov8、Python代码，数据集）

项目介绍 项目中所用到的算法模型和数据集等信息如下&#xff1a; 算法模型&#xff1a;     yolov8 yolov8主要包含以下几种创新&#xff1a;         1. 添加注意力机制&#xff08;SE、CBAM等&#xff09;         2. 修改可变形卷积&#xff08;DySnake-主干c…
阅读更多...
二分查找法详解（6种变形）

二分查找法详解（6种变形）

前言 在之前的博客中&#xff0c;我给大家介绍了最基础的二分查找法&#xff08;没学的话点我点我&#xff01;&#xff09; 今天我将带大家学习二分法的六种变形如何使用&#xff0c;小伙伴们&#xff0c;快来开始今天的学习吧&#xff01; 文章目录 1&#xff0c;查找第一个…
阅读更多...
Ubuntu 常用命令之 du 命令用法介绍

Ubuntu 常用命令之 du 命令用法介绍

&#x1f4d1;Linux/Ubuntu 常用命令归类整理 Ubuntu系统下的du命令是一个用来估计和显示文件和目录所占用的磁盘空间的命令。du是“disk usage”的缩写&#xff0c;这个命令可以帮助用户了解磁盘被哪些文件和目录使用。 du命令的常见参数有 -a&#xff1a;列出所有文件和目…
阅读更多...
Python实验报告十一、自定义类模拟三维向量及其运算

Python实验报告十一、自定义类模拟三维向量及其运算

一、实验目的&#xff1a; 1、了解如何定义一个类。 2、了解如何定义类的私有数据成员和成员方法。 3、了解如何使用自定义类实例化对象。 二、实验内容&#xff1a; 定义一个三维向量类&#xff0c;并定义相应的特殊方法实现两个该类对象之间的加、减运算&#xff08;要…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023