前缀和+单调双队列+贪心：LeetCode2945:找到最大非递减数组的长度-阿里云开发者社区

前缀和+单调双队列+贪心：LeetCode2945:找到最大非递减数组的长度

2024-01-22 30

版权

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

简介： 前缀和+单调双队列+贪心：LeetCode2945:找到最大非递减数组的长度

题目

给你一个下标从 0 开始的整数数组 nums 。

你可以执行任意次操作。每次操作中，你需要选择一个子数组，并将这个子数组用它所包含元素的和替换。比方说，给定数组是 [1,3,5,6] ，你可以选择子数组 [3,5] ，用子数组的和 8 替换掉子数组，然后数组会变为 [1,8,6] 。

请你返回执行任意次操作以后，可以得到的最长非递减数组的长度。

子数组指的是一个数组中一段连续非空的元素序列。

示例 1：

输入：nums = [5,2,2]

输出：1

解释：这个长度为 3 的数组不是非递减的。

我们有 2 种方案使数组长度为 2 。

第一种，选择子数组 [2,2] ，对数组执行操作后得到 [5,4] 。

第二种，选择子数组 [5,2] ，对数组执行操作后得到 [7,2] 。

这两种方案中，数组最后都不是非递减的，所以不是可行的答案。

如果我们选择子数组 [5,2,2] ，并将它替换为 [9] ，数组变成非递减的。

所以答案为 1 。

示例 2：

输入：nums = [1,2,3,4]

输出：4

解释：数组已经是非递减的。所以答案为 4 。

示例 3：

输入：nums = [4,3,2,6]

输出：3

解释：将 [3,2] 替换为 [5] ，得到数组 [4,5,6] ，它是非递减的。

最大可能的答案为 3 。

参数范围：

1 <= nums.length <= 10⁵

1 <= nums[i] <= 10⁵

枚举最后一个子数组nums(j,i]

假定结果向量为vRet

nums[0,j] 需要记录两个子状态：最有一个子数组的和，vRet的长度（操作前的子数组数量）。枚举这些状态时间复杂度O(n)，枚举i时间复杂度O(n)，枚举j时间复杂度O(n)。故总时间复杂度o(n³)。合并nums[0,j]和nums(j,i]有两种操作：

操作一：nums(j,i]全部合并到vRet[j]的最后一个元素。无前提条件。

操作二：nums(j,i]成为新元素。前天条件nums(j,i]大于vRet[j]的最后一个元素。

贪心：不存在len > len2且v1 > v2

令nums[0,i)合法分成n段，最后一段的值为fin，即分成一段，最后的值为fi1，分成两段，最后的值为fi2。

令nums[0,j)…fjn。

证明：对于任意数组（子数组），fxn 一定大与等于fxn+1。x是j,j等…

n==1: fx1 为整个数组的和，fx2为数组第二部分的和。显然成立。

n >1 用反证法：

假定可以合法分成n段，分别为{a1,a2…an}

假定可以合法分成n+1段:分别为(b1,b2…bn,bn+1}。bn+1可能有多个值，取最小值

假定an < bn+1，则{a1,a2,…an-1} 和大于{b1…bn}的和 => 假定前者包括nums[0,i)后者包括nums[0,j) => i >j

则{b1,b2…bn+nums[j,i）}是nums[0,i)的一个合法分成n段,{a1…an-1} 是nums[0,i)一个合法n-1段。

bn+nums[j,i）就是fin, an-1,就是fn-1 fxn-1 >= fnx =>an-1 > bn+nums[j,i)

因为an >= an-1 => {b1,b2…bn+nums[j,i),an} 是一个nums的n+1段划分。

结合假设：an

优化后时间复杂度O(n)

如果nums[0,i)存在长度len，则nums[0,i]一定存在长度为len的结果：将nums[i]追加到最后。

判断nums[0,i]能否则在nums[0,j] 增加一个元素（nums(j,i]的和），需要判断

vPreSum[i+1] - vPreSum[j+1] >= Last[j]

即vPreSump[i+1] >= Last[j]+vPreSum[j+1]

Last[j] 是最后元素的值

Last[j]+vPreSum[j+1] 可以合并一个变量llPre。已知状态只需要保留最大长度，长度相同保留llPre最小。

此解法错误，还在摸索中。

class Solution {
public:
  int findMaximumLength(vector<int>& nums) {
    m_c = nums.size();
    auto vPreSum = CreatePreSum(nums);
    int len = 0;
    long long llPre = 0;
    int preIndex = -1;
    for (int i = 0; i < m_c; i++)
    {
      if (vPreSum[i + 1] >= llPre)
      {
        len++;
        llPre = vPreSum[i+1] + (vPreSum[i + 1] - vPreSum[preIndex + 1]);
        preIndex = i;
      }
      else
      {
        const long long curAdd  = vPreSum[i+1] - vPreSum[preIndex+1] + (vPreSum[i + 1] - vPreSum[preIndex + 1]);
        if (curAdd < 0)
        {
          llPre += curAdd;
          preIndex = i;
        }
      }
    }
    return len;
  }
  int m_c;
};

正确解法

下标从小到大遍历nums[i]，queIndexs记录[0,i)，淘汰以下：

一，j1 < j2，也就(j1,i]的和大于(j2,i]。也就是j1的最后一个数大于j2的最后一个数。llPre1 大于llPre2，也就llPre1更难匹配，淘汰j1。淘汰后：下标升序 llPre 降序。

二，j找到第一个i后，淘汰。假定j的长度为len,i1 < i2。i1可以选择{… (j,i1],(i1,i2]} 和{…{j,i2]}，而i2只能选择后者，所以i1不劣与i2。

注意：如果无法长度+1，则vLast[i] = vLast[i - 1] + nums[i]

队首元素的长度和队尾元素的长度相差不会超过1

双向队列中的下标升序，也就是长度升序。

假定新入队的长度是len，则被淘汰的队首长度为len-1。由于是升序，所以队中元素的长度都大于等于len-1，小于等于len

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 findMaximumLength(vector<int>& nums) {
    m_c = nums.size();
    auto vPreSum = CreatePreSum(nums);
    vector<int> vRet(m_c,1),vLast(m_c,nums.front());
    std::deque<int> queIndexs;
    queIndexs.emplace_back(0);
    auto Pre = [&](const int index) {return vPreSum[index + 1] + vLast[index];  };
    for (int i = 1; i < m_c; i++)
    {
      vRet[i] = vRet[i - 1];
      vLast[i] = vLast[i - 1] + nums[i];
      while (queIndexs.size() && (vPreSum[i + 1] >= Pre(queIndexs.front())))
      {
        vRet[i] = vRet[queIndexs.front()]+1;
        vLast[i] = vPreSum[i + 1] - vPreSum[queIndexs.front() + 1];
        queIndexs.pop_front();
      }
      while (queIndexs.size() && (Pre(queIndexs.back()) >= Pre(i)))
      {
        queIndexs.pop_back();
      }
      queIndexs.emplace_back(i);
    }
    return vRet.back();
  }
  int m_c;
};

错误解法

class Solution {
public:
int findMaximumLength(vector& nums) {
stack sta;
int i = 0;
while (i < nums.size())
{
long long cur = 0;
while (sta.size() && (i < nums.size()) && (sta.top() > cur + nums[i]))
{
cur += nums[i++];
}
if (i >= nums.size())
{
break;//理论上需要栈顶的值，由于我需要的是数量，所以可以不修改
}
sta.emplace(cur+ nums[i++]);
}
return sta.size();
}
};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步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++ 实现。