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

这篇具有很好参考价值的文章主要介绍了前缀和+单调双队列+贪心:LeetCode2945:找到最大非递减数组的长度。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

本文涉及知识点

C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
单调双队列 贪心

题目

给你一个下标从 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 <= 105
1 <= nums[i] <= 105

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

假定结果向量为vRet
nums[0,j] 需要记录两个子状态:最有一个子数组的和,vRet的长度(操作前的子数组数量)。枚举这些状态时间复杂度O(n),枚举i时间复杂度O(n),枚举j时间复杂度O(n)。故总时间复杂度o(n3)。合并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 <bn+1 和 bn+1是最小值矛盾

优化后时间复杂度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();
}
};

前缀和+单调双队列+贪心:LeetCode2945:找到最大非递减数组的长度,# 算法题,算法,leetcode,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++ 实现。

前缀和+单调双队列+贪心:LeetCode2945:找到最大非递减数组的长度,# 算法题,算法,leetcode,c++,前缀和,单调双向队列,贪心,数学证明文章来源地址https://www.toymoban.com/news/detail-773434.html

到了这里,关于前缀和+单调双队列+贪心:LeetCode2945:找到最大非递减数组的长度的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

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

    map|动态规划|单调栈|LeetCode975:奇偶跳 单调栈分类、封装和总结 C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 作为国王的统治者,你有一支巫师军队听你指挥。 给你一个下标从 0 开始的整数数组 strength ,其中 strength[i] 表示第 i 位巫师的力量值

    2024年02月02日
    浏览(30)
  • 【算法题解】23. 「滑动窗口最大值」单调队列解法

    这是一道 困难 题 题目来自:https://leetcode.cn/problems/sliding-window-maximum/ 给你一个整数数组 nums ,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例 1: 示

    2023年04月11日
    浏览(53)
  • 蓝桥杯刷题016——最大子矩阵(尺取法+单调队列)

    题目来源:最大子矩阵 - 蓝桥云课 (lanqiao.cn) 问题描述 小明有一个大小为 N×M 的矩阵, 可以理解为一个 N 行 M 列的二维数组。 我们定义一个矩阵 m 的 稳定度 f(m)  为 f(m)=max(m)−min(m) , 其中 max(m) 表示矩阵 m 中的最大值, min(m) 表示矩阵 m 中的最小值。 现在小明想要从

    2023年04月16日
    浏览(33)
  • 算法训练day37|贪心算法 part06(LeetCode738.单调递增的数字)

    题目链接🔥🔥 给定一个非负整数 N,找出小于或等于 N 的最大的整数,同时这个整数需要满足其各个位数上的数字是单调递增。 (当且仅当每个相邻位数上的数字 x 和 y 满足 x = y 时,我们称这个整数是单调递增的。) 示例 1: 输入: N = 10 输出: 9 示例 2: 输入: N = 1234 输出:

    2024年02月09日
    浏览(35)
  • leetcode分类刷题:队列(Queue)(一、单调队列)

    单调队列,看起来是与单调栈对应起来的一样;但是做题的时候感觉单调队列不像单调栈一样,能根据题意自然形成 单调队列的基本实现 ,感觉单调队列更像是和某个队列对应起来的一样 1、 单调队列的经典题型 :使用双向队列维护窗口,窗口移动的元素增删与队列的先进

    2024年02月09日
    浏览(41)
  • 滑动窗口最大值 | 单调队列解题思路与实现,前 K 个高频元素

    学习LeetCode 239与347题目的解题思路与实现方法,包括单调队列与优先级队列(堆)的应用。掌握滑动窗口的最大值与前K个高频元素的解决方案。

    2024年02月13日
    浏览(49)
  • LeetCode 239.滑动窗口的最大值 Hot100 单调栈

    给你一个整数数组  nums ,有一个大小为  k   的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的  k  个数字。滑动窗口每次只向右移动一位。 返回  滑动窗口中的最大值  。 示例 1: 示例 2: 提示: 1 = nums.length = 105 -104 = nums[i] = 104 1 = k = num

    2024年02月20日
    浏览(51)
  • 算法打卡day32|贪心算法篇06|Leetcode 738.单调递增的数字、968.监控二叉树

    Leetcode 738.单调递增的数字 题目链接:738.单调递增的数字  大佬视频讲解:单调递增的数字视频讲解  个人思路 这个题目就是从例子中找规律,例如 332,从后往前遍历,32不是单调递增将2变为9,3减1,变成了329,遍历到2,32不是递增,将2变为9,3减1,变成299,符合题目条件,打印

    2024年04月16日
    浏览(45)
  • 【LeetCode题目详解】第八章 贪心算法 part06 738.单调递增的数字 968.监控二叉树 (day37补)

    当且仅当每个相邻位数上的数字  x  和  y  满足  x = y  时,我们称这个整数是 单调递增 的。 给定一个整数 n ,返回 小于或等于 n 的最大数字,且数字呈 单调递增 。 示例 1: 示例 2: 示例 3: 提示: 0 = n = 109 # 暴力解法 题意很简单,那么首先想的就是暴力解法了,来我替大家

    2024年02月10日
    浏览(41)
  • 【leetcode:1944. 队列中可以看到的人数】单调栈算法及其相关问题

    1944. 队列中可以看到的人数 有  n  个人排成一个队列, 从左到右  编号为  0  到  n - 1  。给你以一个整数数组  heights  ,每个整数  互不相同 , heights[i]  表示第  i  个人的高度。 一个人能  看到  他右边另一个人的条件是这两人之间的所有人都比他们两人  矮  。更

    2024年01月25日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包