单调栈
C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
作为国王的统治者,你有一支巫师军队听你指挥。
给你一个下标从 0 开始的整数数组 strength ,其中 strength[i] 表示第 i 位巫师的力量值。对于连续的一组巫师(也就是这些巫师的力量值是 strength 的 子数组),总力量 定义为以下两个值的 乘积 :
巫师中 最弱 的能力值。
组中所有巫师的个人力量值 之和 。
请你返回 所有 巫师组的 总 力量之和。由于答案可能很大,请将答案对 109 + 7 取余 后返回。
子数组 是一个数组里 非空 连续子序列。
示例 1:
输入:strength = [1,3,1,2]
输出:44
解释:以下是所有连续巫师组:
输入:strength = [5,4,6]
输出:213
解释:以下是所有连续巫师组:
时间复杂度: 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);
}
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++ 实现。