AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【单调栈】LeetCode:2818操作使得分最大

2024-01-22 48
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【单调栈】LeetCode:2818操作使得分最大

题目

给你一个长度为 n 的正整数数组 nums 和一个整数 k 。

一开始，你的分数为 1 。你可以进行以下操作至多 k 次，目标是使你的分数最大：

选择一个之前没有选过的 非空 子数组 nums[l, …, r] 。

从 nums[l, …, r] 里面选择一个 质数分数 最高的元素 x 。如果多个元素质数分数相同且最高，选择下标最小的一个。

将你的分数乘以 x 。

nums[l, …, r] 表示 nums 中起始下标为 l ，结束下标为 r 的子数组，两个端点都包含。

一个整数的 质数分数 等于 x 不同质因子的数目。比方说， 300 的质数分数为 3 ，因为 300 = 2 * 2 * 3 * 5 * 5 。

请你返回进行至多 k 次操作后，可以得到的 最大分数 。

由于答案可能很大，请你将结果对 109 + 7 取余后返回。

示例 1：

输入：nums = [8,3,9,3,8], k = 2

输出：81

解释：进行以下操作可以得到分数 81 ：

  • 选择子数组 nums[2, …, 2] 。nums[2] 是子数组中唯一的元素。所以我们将分数乘以 nums[2] ，分数变为 1 * 9 = 9 。
  • 选择子数组 nums[2, …, 3] 。nums[2] 和 nums[3] 质数分数都为 1 ，但是 nums[2] 下标更小。所以我们将分数乘以 nums[2] ，分数变为 9 * 9 = 81 。
    81 是可以得到的最高得分。
    示例 2：
    输入：nums = [19,12,14,6,10,18], k = 3
    输出：4788
    解释：进行以下操作可以得到分数 4788 ：
  • 选择子数组 nums[0, …, 0] 。nums[0] 是子数组中唯一的元素。所以我们将分数乘以 nums[0] ，分数变为 1 * 19 = 19 。
  • 选择子数组 nums[5, …, 5] 。nums[5] 是子数组中唯一的元素。所以我们将分数乘以 nums[5] ，分数变为 19 * 18 = 342 。
  • 选择子数组 nums[2, …, 3] 。nums[2] 和 nums[3] 质数分数都为 2，但是 nums[2] 下标更小。所以我们将分数乘以 nums[2] ，分数变为 342 * 14 = 4788 。
    4788 是可以得到的最高的分。
    参数范围：
    1 <= nums.length == n <= 105
    1 <= nums[i] <= 105
    1 <= k <= min(n * (n + 1) / 2, 109)

单调栈

时间复杂度😮(nlogn)

静态变量vPrime 记录所有质数。

vPriCount 记录nums各数的质量分数。vPriCount也可以弄成静态成员变量。

我们枚举各子数组的最大质量分数，如果有多个最大质量分数，取下标最小的。即：

left为从右向左第一个大于等于vPriCount[i]的下标，不存在为-1。

right为从左向右第一个大于vPriCount[i]的下标，不存在为m_c。

子数组(li,ri)就是符合条件的子数组，li取值范围(left,i]，ri取值范围[i,right)。

我们按的nums[i]降序操作 最大质量分数为vPriCount[i]的子数组。

代码

核心代码

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]。
};
vector<int> CreatePrime(int iMax)
{
  vector<int> vPrime = { 2 };
  for (int i = 3; i <= iMax; i++)
  {
    bool b = true;
    for (const auto& n : vPrime)
    {
      if (0 == i % n)
      {
        b = false;
        break;
      }
    }
    if (b)
    {
      vPrime.emplace_back(i);
    }
  }
  return vPrime;
}
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 Solution {
public:
  int maximumScore(vector<int>& nums, int k) {
    m_c = nums.size();
    vector<int> vPriCount;
    {
      static vector<int> vPrime = CreatePrime(1000 * 100);
      for (const auto& n : nums)
      {
        int tmp = n;
        int iNum = 0;
        for (const auto& pr : vPrime)
        {
          if (pr * pr > tmp)
          {
            break;
          }
          if (0 == tmp % pr)
          {
            while (0 == tmp % pr)
            {
              tmp /= pr;
            }
            iNum++;
          }
        }
        vPriCount.emplace_back(iNum + (tmp > 1));
      }
    }
    CRangIndex ri(vPriCount, [&](int i1, int i2) {return vPriCount[i1] > vPriCount[i2]; });
    std::multimap<int, int, greater<int>> mValueIndex;
    for (int i = 0; i < ri.m_c; i++)
    {
      mValueIndex.emplace(nums[i], i);
    }
    C1097Int<> biRet=1;
    for (const auto& [value, i] : mValueIndex)
    {
      const long long llSubArrCount = ((long long)i - ri.m_vLeft[i]) * (ri.m_vRight[i] - i);
      const long long llOpeCount = min((long long)k, llSubArrCount);
      biRet *= C1097Int<>(value).pow(llOpeCount);
      k -= llOpeCount;
      if (0 == k)
      {
        break;
      }
    }
    return biRet.ToInt();
  }
  int m_c;
};

测试用例

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> nums;
  int k;
  {
    Solution slu;
    nums = { 8, 3, 9, 3, 8 };
    k = 2;
    auto res = slu.maximumScore(nums, k);
    Assert(81, res);
  }
  {
    Solution slu;
    nums = { 19,12,14,6,10,18 };
    k = 3;
    auto res = slu.maximumScore(nums, k);
    Assert(4788, res);
  }
  //CConsole::Out(res);
}

2023年8月

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(int 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;;
};
template<int MOD = 1000000007>
int operator+(int iData, const C1097Int<MOD>& int1097)
{
  int iRet = int1097.operator+(C1097Int<MOD>(iData)).ToInt();
  return iRet;
}
template<int MOD = 1000000007>
int& operator+=(int& iData, const C1097Int<MOD>& int1097)
{
  iData = int1097.operator+(C1097Int<MOD>(iData)).ToInt();
  return iData;
}
template<int MOD = 1000000007>
int operator*(int iData, const C1097Int<MOD>& int1097)
{
  int iRet = int1097.operator*(C1097Int(iData)).ToInt();
  return iRet;
}
template<int MOD = 1000000007>
int& operator*=(int& iData, const C1097Int<MOD>& int1097)
{
  iData = int1097.operator*(C1097Int(iData)).ToInt();
  return iData;
}
class Solution {
public:
  int maximumScore(vector<int>& nums, int k) {
    m_c = nums.size();
    vector<int> vScore;
    for ( int n : nums)
    {
      int iScore = 0;
      for (int i = 2; i * i <= n; i++)
      {
        if (0 != n % i)
        {
          continue;
        }
        iScore++;
        while (0 == n % i)
        {
          n /= i;
        }
      }
      if (n > 1)
      {
        iScore++;
      }
      vScore.emplace_back(iScore);
    }
    stack<int> sta;
    vector<int> vLeft(m_c), vRight(m_c, m_c);
    for (int i = 0 ; i < m_c ; i++ )
    {
      while (sta.size() && (vScore[sta.top()] < vScore[i]))
      {
        vRight[sta.top()] = i;
        sta.pop();
      }
      vLeft[i] = sta.size() ? sta.top() : -1;
      sta.emplace(i);     
    }
    std::map<int, long long,std::greater<int>> mValueNum;
    for (int i = 0; i < m_c; i++)
    {
      mValueNum[nums[i]] += (i - vLeft[i])*(long long)(vRight[i] - i);
    }
    C1097Int<> biRet = 1;
    while (k > 0)
    {
      for (auto it : mValueNum)
      {
        long long llMulMul = min((long long)k, it.second);
        k -= llMulMul;
        auto cur = C1097Int<>(it.first).pow((int)llMulMul);
        biRet *= cur;
      }
    }
    return biRet.ToInt();
  }
  int m_c;
};

使用封装类后

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(int iVectorSize, _Pr CurIndexCmpStackTopIndex)
  {
    m_c = iVectorSize;
    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);
    }
  }
  template<class _Pr>
  CRangIndex(const vector<int>& nums, _Pr CurValueCmpStackTopValue)
  {
    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() && (CurValueCmpStackTopValue(nums[i], nums[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]。
};
vector<int> CreatePrime(int iMax)
{
  vector<int> vPrime = { 2 };
  for (int i = 3; i <= iMax; i++)
  {
    bool b = true;
    for (const auto& n : vPrime)
    {
      if (0 == i % n)
      {
        b = false;
        break;
      }
    }
    if (b)
    {
      vPrime.emplace_back(i);
    }
  }
  return vPrime;
}
class Solution {
public:
  int maximumScore(vector<int>& nums, int k) {
    m_c = nums.size();
    vector<int> vPriCount;
    {
      static vector<int> vPrime = CreatePrime(1000 * 100);
      for (const auto& n : nums)
      {
        int tmp = n;
        int iNum = 0;
        for (const auto& pr : vPrime)
        {
          if (pr * pr > tmp)
          {
            break;
          }
          if (0 == tmp % pr)
          {
            while (0 == tmp % pr)
            {
              tmp /= pr;
            }
            iNum++;
          }
        }
        vPriCount.emplace_back(iNum + (tmp > 1));
      }
    }
    CRangIndex ri(vPriCount, std::greater<>());
    std::multimap<int, int, greater<int>> mValueIndex;
    for (int i = 0; i < ri.m_c; i++)
    {
      mValueIndex.emplace(nums[i], i);
    }
    C1097Int<> biRet=1;
    for (const auto& [value, i] : mValueIndex)
    {
      const long long llSubArrCount = ((long long)i - ri.m_vLeft[i]) * (ri.m_vRight[i] - i);
      const long long llOpeCount = min((long long)k, llSubArrCount);
      biRet *= C1097Int<>(value).pow(llOpeCount);
      k -= llOpeCount;
      if (0 == k)
      {
        break;
      }
    }
    return biRet.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++ 实现。

文章标签：
算法
C++
测试技术
C#
机器学习/深度学习
关键词：
LeetCode操作
栈LeetCode
单调LeetCode
单调栈LeetCode
闻缺陷则喜何志丹
目录
相关文章
码农阿豪
|
5月前
|
存储 算法 测试技术
力扣经典150题第五十四题：最小栈
力扣经典150题第五十四题：最小栈
码农阿豪
44 0
nsu_xxy
|
6月前
|
存储 算法 索引
力扣每日一题 6/24 模拟 数组 单调栈
力扣每日一题 6/24 模拟 数组 单调栈
nsu_xxy
39 0
Codelinghu
|
2月前
【LeetCode 24】225.用队列实现栈
【LeetCode 24】225.用队列实现栈
Codelinghu
12 0
Codelinghu
|
2月前
|
算法
【LeetCode 23】232.用栈实现队列
【LeetCode 23】232.用栈实现队列
Codelinghu
25 0
BetterBench
|
4月前
|
Python
【Leetcode刷题Python】946. 验证栈序列
LeetCode题目“946. 验证栈序列”的Python解决方案，通过模拟栈的压入和弹出操作来验证给定的两个序列是否能通过合法的栈操作得到。
BetterBench
33 6
BetterBench
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 30. 包含min函数的栈
本文提供了实现一个包含min函数的栈的Python代码，确保min、push和pop操作的时间复杂度为O(1)。
BetterBench
32 4
BetterBench
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 09. 用两个栈实现队列
使用两个栈实现队列的Python解决方案，包括初始化两个栈、实现在队列尾部添加整数的appendTail方法和在队列头部删除整数的deleteHead方法，以及相应的示例操作。
BetterBench
41 2
BetterBench
|
4月前
|
Python
【Leetcode刷题Python】232. 用栈实现队列
如何使用Python语言通过两个栈来实现队列的所有基本操作，包括入队(push)、出队(pop)、查看队首元素(peek)和判断队列是否为空(empty)，并提供了相应的代码实现。
BetterBench
22 0
一只大鸽子
|
6月前
|
存储 算法 Python
二刷力扣--栈和队列
二刷力扣--栈和队列
一只大鸽子
39 1
西柚与蓝莓
|
5月前
|
Python
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
西柚与蓝莓
54 0