普通视图
每日一题-统计极差最大为 K 的分割方式数🟡
给你一个整数数组 nums 和一个整数 k。你的任务是将 nums 分割成一个或多个 非空 的连续子段,使得每个子段的 最大值 与 最小值 之间的差值 不超过 k。
返回在此条件下将 nums 分割的总方法数。
由于答案可能非常大,返回结果需要对 109 + 7 取余数。
示例 1:
输入: nums = [9,4,1,3,7], k = 4
输出: 6
解释:
共有 6 种有效的分割方式,使得每个子段中的最大值与最小值之差不超过 k = 4:
[[9], [4], [1], [3], [7]][[9], [4], [1], [3, 7]][[9], [4], [1, 3], [7]][[9], [4, 1], [3], [7]][[9], [4, 1], [3, 7]][[9], [4, 1, 3], [7]]
示例 2:
输入: nums = [3,3,4], k = 0
输出: 2
解释:
共有 2 种有效的分割方式,满足给定条件:
[[3], [3], [4]][[3, 3], [4]]
提示:
2 <= nums.length <= 5 * 1041 <= nums[i] <= 1090 <= k <= 109
当我最后一道职业护城河正在溃堤
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
11月末,北京初冬。
今年36氪的WISE大会遇上了好天气。无云的蓝天下,抵达798的观众路过巨大的红砖烟囱和电子广告屏走入会场。
和往年相比,现场展位区多了不少先进制造类公司的硬件展示。跟随着表演机器人往会场深处走,你会看见人们围在某个角落里的煎饼机器身边,观赏它乐此不疲地运转。
在通往二楼主会场区的阶梯前,一些人会注意到我们的「职场红利派对」——或许,是市场部的同事希望用“派对”一词来消解职场话题中无处可逃的“班味”;又或许,是我们的职场环境每年都面临着愈发严峻的挑战(你看,就连摊煎饼的工作都有可能会被机器取代)。苦中作乐的思想派对,不失为一种时代狂浪中坚持观察、思考和分享的宣言。
“蓝领白领,职面风景”是这次WISE职场分会场沙龙的Slogan。某一天,你发现白领同事们悄悄有了蓝领副业,蓝领师傅们有了转型为白领的机会。还有一些职业,它足够“复合”,你也说不清它到底是动脑还是动手更多。而过去职业固有的三六九等、稀缺价值衡量标准,早已被新的生产工具和国家意志打破。
蓝领与白领的并轨背后,是AI工具的普及,以及中国市场往先进制造发展转型的浪潮。《职场Bonus》想要为个体解读这其中所包含的转折点、非共识和信息差,于是邀请了最懂这个话题的人才平台、高管教练、咨询师、创业者、猎头顾问、学界先锋观察者……总计15位嘉宾。
在这里,也感谢他们愿意发声和赴约,分享各自相信的,与看见的。
办一场活动不容易。除去现场的案例演示、游戏互动,我们把在这2日沙龙活动中听到的思想精华萃取,供远方的你,我们的朋友,共同参考。
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
💭
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
王晓涵
金色船文化 创始人,中央戏剧学院在读研究生
• 我们一定要忘记自己的专业对口,要思考我们的能力如何迁移,要把我们自己放在了一个非常有主体性的位置,才能在红海的纵深里开辟属于自己的蓝海。
• 我作为全国唯一中戏背景的银发经济创业者,最初用非遗手作打开市场,但很快意识到天花板太低。后来我通过把心理疏导功能专业化,让老年人在情景重现和角色互换中解决衰老焦虑,建立起戏剧疗愈的壁垒。
💭
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
任鹏飞
禾蛙 迅致业务负责人
• 职场红利是时代红利下每个人努力和选择的结果,在整个职场中,我们要不断抓住职场红利,让自己的职业生涯持续发展,让自己越来越值钱。
• 而想要抓住职场红利,技能非常重要。在当下,蓝领、灰领、白领界限渐趋融合,许多曾经非常受欢迎的,如Java工程师已经从全职白领降档为外包,反而是懂技术、有语言基础的一线蓝领的收入越来越高。
•个人能力、价值才是帮助大家抓住时代红利的关键。比如很多大厂的HR虽然根本不懂编程,却开始学习用AI工具进行编程,以此来完成会议纪要本地化转写等工作——这样就既满足了保密要求,又提高了工作效率。
💭
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
林耿旭
低聚体 创始人
• AI时代是放大器,能放大个人才能创意,也会放大懒惰。善用者如虎添翼,科普UP主“大圆镜科普”用AI生成画面达成百万粉;但更多人的能力鸿沟正被急剧拉大。
• 在AI时代,我认为有三个生存能力非常重要,即:资讯捕捉、学习与执行力。有专长的个体将迎来黄金发展期,超级个体和超级“小”团队将成为职业发展的新趋势。
• AI一天,人间一年。如果你一周不看任何资讯,就会感觉自己好像被时代淘汰了。当然,捕捉信息后要及时探索、学习、并尝试将其内化,应用到生活和工作中。
💭
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
陈怡静
创业顾问,《无畏沟通》 作者
• 自由职业对专业度的要求其实比打工更高,因此绝不能将其作为逃避职业问题的避风港。
• 过去一年里,我持续回答两个核心问题:钱和健康。我现在每年12月雷打不动地做个人资产负债表与现金流量表,财务安全才有决策自由。
• 在自由职业的旷野待久了必然恐慌,但任何被你放下过的选择都能随时重新摆回台面审视,唯独切忌一条路走到黑。
💭
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
郑宁
中国传媒大学 教授
• 新职业有六大风险:内容合规、合同陷阱、税务偷逃税、知识产权、数据合规、商业秘密。
• 关键要过程留痕存证据,合同盯紧核心条款,专业问题务必寻求专业人士帮助。AI领域目前需从业者、创业者保持警惕,训练数据合法性、生成作品著作权归属均存在争议,属于待完善的灰色地带。
💭
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
七芊
职场作家,选择力 创始人
• 真正耽误我们去找到新职业的,是内心深处的自卑。突破这个自卑的核心在于敢于去了解那些跟你完全不匹配的好工作。
• 但凡是和人相关的复盘,你们都要从出身、学历、履历和他的性格进行总结,描绘出你自己的贵人画像和小人画像。
• 和事件相关的复盘,则要侧重于你从小到大所有关键节点上面,弄明白你的成功要素和失败要素到底是什么。
💭
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
胡漾
观心实验室 品牌VP
• AI会取代蓝领和白领的重复劳动,人类的核心竞争力是“与生命相关的技能”,如唱歌、心理疗愈、手工创作。
• 今年一方面大厂裁员,另一方面新兴行业急需人才,职场存在严重错配。现在不应该继续迷信“铁饭碗”,这个世界上没有稳定的结构,只有解决具体问题的能力。
• 所以,“下地”干活吧!焦虑的终点都是具体问题,与其内耗,不如和真实世界碰撞,解决一个小问题。找个“不焦虑的搭子”,把焦虑写在纸上,一半焦虑会消失;两人一起分担,焦虑就只剩25%。
💭
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
黄雷
策御国际传播 创始人
• 自由职业是不得已而为之的,并不是一个选择。但当你作为一个自由职业者的时候,你应该思考,你能够让自己安身立命、养家糊口的那个最硬的能力到底是什么?
• 打工和自由职业相比,“只有一条轨道”有的时候是幸福的,你知道要往哪去,每天要干嘛。但是当你处在旷野的时候,你要开始想一件事情:你要把你未来的生命,投入到哪一件事情上面?在曾经那个外企、互联网企业蓬勃发展的年代,你不需要任何这样的思考就可以拿一份很好的薪水。但现在这些机会已经没有了。在这样的前提下,如果你不先好好思考就骤然置身旷野,人是会崩溃的。
• 我在想,如果能让我再重活一次,我一定会花出待在大厂里30%的时间去思考,如果我失去现在的title 了,我到底需要做什么,我愿意为什么东西投入我的精力和生命?
💭
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
郭彪
精匠通途 创始人
• AI对眼下的制造业实质性影响有限。但随着时间推移,AI技术一定会渗透到各行各业,到那时,如果知识结构还没有迭代,就会面临较大的冲击。
• 说到底,新旧生产力更替,旧岗位消失,新岗位总会冒出来,但前提是你得让自己成为能驾驭新技术的人。
• 目前95后车间主任比比皆是,他们技校毕业十八九岁,工作五六年,二十五六岁就管几十号人,晋升比白领快多了。
💭
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
魏鑫
北京睿成半导体 HR负责人
• 机械加工领域的部分急缺岗位月薪达五位数以上,但市场仍处于有缺口且有挑选机会的状态。
• 一线工作中的安全隐患都是存在的,但企业对这些危害因素的防护都很重视,全力降低危险系数。现在的车间都是5S管理,恒温恒湿,洁净区域,跟想象中的噪音灰尘完全不一样。
• AI时代下,自动化越完善,流水线岗位需求自然越低,对于机器或者手工作业,产品单一且要求复杂,自动化替代周期会长得多。保住饭碗关键在于是否真想做好这份工作、能否持续自我提升。
💭
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
王希娜
前领英、阿里、雅思 营销高管
• 个人职场发展的红利,与时代红利高度相关,也与自己个人价值的追寻密不可分。过去这些年,我从智能设备到移动互联网,再到大数据、 AI,从市场调研转到互联网,在百度、领英、阿里这几家公司得到了很好的发展。到了一定的阶段,我更希望让自己的价值通过培养下一代、为年轻人赋能来体现,于是转到了教育行业。
• 所以我们要在“追红利”和“找自己”之间寻求平衡与融合。你越是了解自己、滋养自己,就越能在AI时代立于不败之地。
• 发掘自己有天赋优势的、可迁移的、难以被 AI 替代的能力尤其重要。比如说对人性的洞察,与人深度沟通的能力,对大势和策略的直觉性把握。更深层次地,我们要去耕耘自己身心的健康,“留得青山在”,让自己有一个健康的身体、健全的心智,不断提升对世界的认知,以此为甲,保护自己穿越任何的周期,即使在低谷的时候,也能够平和欢喜地忍耐,内心也常驻着希望。
💭
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
汤悦铭
云耕九州文旅科技集团 市场营销总监
• 文旅短剧投入小回报大,几十万成本可达上亿播放。我们团队目前已成功打造出锦州市文旅短剧《锦州烧烤侠》,昆山市昆曲主题短剧《玉见梁辰鱼》及肌肤未来品牌定制剧,曝光超20亿。全国6个文旅基地、政府给产业园、资金和人才支持,能带货带人带经济。
• 目前文旅短剧的人才缺口极大,且短剧会为普通人创造机会,从业不需要专业经验,素人也可以做编导、演员、运营。我们早在2017、2018年就布局,建立起产业链完整、能将海外创作者资源链接起来的核心优势。
💭
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
威尔王
播客《职业离想》主播
• 我小时候的快乐就是开心地聊天,希望2026年能有更多机会像这样聊天。
💭
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
孙丹
独立内容创作者
(也是这次WISE职场红利派对的项目经理、幕后志愿者之一)
• 我的职业经历分三段:百胜餐饮储备经理、36氪氪咖啡孵化项目负责人、食品垂类小程序联创。
• 在餐饮行业的8年经历,让我练就吃苦耐劳和培训加盟商的能力,这帮助我在36氪内部孵化氪咖啡时,7个月内在8城开10店。我离开36氪后,把门店运营、内容撰写、活动策划能力整合,做了一个食品垂类小程序,帮助国内食品达人拓展线上销售和出海,并持续通过播客等传播方式为品牌赋能。我能做这么多事情的核心就是可迁移能力的整合复用。
💭
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
陈桐
《职场Bonus》 主编
• 蓝领白领现在处于互相交融的时代,一些蓝领工种的薪资,比部分文科生岗位的起薪甚至工作几年后的薪酬还要高。比如月嫂,高端制造行业里需要“手脑共用”的装配工程师,一线城市的新能源汽车售后维修工程师等。
• 外卖员属于蓝领里面门槛不高的职位,受益于媒体的舆论监督,各平台对骑手们的规则和福利有所改善,这两年从业者的幸福指数有了明显上升。需要注意的是,这一岗位本质上高度依赖于大型商业体系统和算法,骑手难以从平台独立。相比之下,健身教练、按摩师傅等其他直接面向C端提供服务的职业不仅收入上限更高,也更适合作为白领的后备副业。如果你懂得做定制化包装,给客户提供包含情绪价值的咨询服务、解决方案,你还有机会把这份蓝领职业变成自己的生意,跳出平台独立开自己的工作室。
💭
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
余雯君
职升未来 CEO
(也是《职场Bonus》最早的项目发起人,@麻吉有三思 视频博主)
• 今年求职者心态是求稳:与其跳更高,先要防止自己坠落。但我们也看到有一些人,更愿意接受降薪,换取去到新兴红利行业的机会。
• 2025年,一线城市的人才流动也表现出新变化:上海仍是最吸引人才的目的地,深圳今年追平上海,杭州、广州吸引力增强。人才从地产、互联网溢出,流向数字智能、先进制造和跨境出海等领域。即使前方有非常多的不确定性和困难,勇敢的人总能先享受世界。
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
● 线下短剧《实习生》现场,由中戏表演系毕业研究生袁咏诗(画着黑眼圈的这位)、中戏表演系在读博士马印民携手呈现
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
![]()
● WISE大会的观众对干货分享的记录绝不含糊
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
![]()
● 戴好手环后发现,懒人沙发躺平区域已经从空座到满座
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
![]()
● 不会手作咖啡的播客主理人不是好主持,不参加趣味挑战的观众拿不到好奖品
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
![]()
36氪「职场Bonus」(ID:ZhiChangHongLi)
● 感谢所有赞助职场红利派对的雇主企业伙伴们,他们是Xmind、好望水、行云集团、大人糖、海螺AI,期待明年还能有更多赞助嘻嘻
![]()
● 职场红利派对门口的“36氪发展史”介绍墙。15年来,36氪以专业和创新为驱动不断成长。
最后,感谢母品牌36氪。
《职场Bonus》将继续和36氪在一起,从人事报道、求职招聘风向报道角度出发,建立那座“孕育万物的、承载新商业文明的岛屿”。
「2025 方舟计划」里,【秋季活动】和【冬季活动】没能如去年规划般和大家见面,延期至明年举办。
而《猎头市场水温调研》、《职场红利雇主Top50名册》、《职场红利年终盘点》系列已于WISE 2025 职场红利派对、创新香港TalentX人才嘉年华现场进行了小规模的线下发布,线上文章将于12月陆续上线,敬请期待!
欢迎体验我们的自研AI产品职升机AI,在红利赛道里找到适合你的机会
关注+星标
让你不再错过
从香港竹脚手架到前端脚手架:那些"借来"的发展智慧与安全警示
Flutter组件封装:验证码倒计时按钮 TimerButton
C#异常概念与try-catch入门
怎么设计一个加密货币 谁有权利发行数字货币 怎么防止double spending attack 怎么验证交易合法性 铸币交易..
4.BTC-协议-北大肖臻老师客堂笔记
Next.js 16 Page Router 国际化 🌐
前端文本分割工具,“他”来了
nvm安装node低版本失败-解决方案
iOS 手机无法播放视频问题排查与解决方案记录
大文件上传实战:基于Express、分片、Web Worker与压缩的完整方案
git提交代码失败?本地代码被清空了?git代码丢了怎么办?三步帮你找回来
dp + 单调队列 + 前缀和,详细思考路径
划分型 DP + 单调队列优化(Python/Java/C++/Go)
O(n^2) 做法
本题是标准的划分型 DP,见 DP 题单 的「§5.2 最优划分」。
一般定义 $f[i+1]$ 表示前缀 $\textit{nums}[0]$ 到 $\textit{nums}[i]$ 在题目约束下,分割出的最少(最多)子数组个数,本题是定义成分割方案数。这里 $i+1$ 是为了把 $f[0]$ 当作初始值。
枚举最后一个子数组的左端点 $j$,那么问题变成前缀 $\textit{nums}[0]$ 到 $\textit{nums}[j-1]$ 在题目约束下的分割方案数,即 $f[j]$。
当子数组右端点 $i$ 固定时,由于子数组越长,最大值越大,最小值越小,最大最小的差值越可能大于 $k$。所以符合要求的左端点 $j$ 一定在一个连续区间 $[L,i]$ 中。累加 $f[j]$ 得
$$
f[i+1] = \sum_{j=L}^{i} f[j]
$$
初始值 $f[0] = 1$,空子数组算一个方案。也可以从递归的角度理解,递归到空子数组,就表示我们找到了一个合法分割方案。
答案为 $f[n]$。
O(n) 做法
由于 $i$ 越大,$L$ 也越大,可以用 滑动窗口【基础算法精讲 03】。
同时,我们需要计算 239. 滑动窗口最大值 和滑动窗口最小值,这可以用 单调队列【基础算法精讲 27】解决。
维护窗口中的 $\displaystyle\sum_{j=L}^{i} f[j]$,记作 $\textit{sumF}$,转移方程优化成
$$
f[i+1] = \textit{sumF}
$$
注意取模。关于模运算的知识点,见 模运算的世界:当加减乘除遇上取模。
本题视频讲解,欢迎点赞关注~
###py
class Solution:
def countPartitions(self, nums: List[int], k: int) -> int:
MOD = 1_000_000_007
n = len(nums)
min_q = deque()
max_q = deque()
f = [0] * (n + 1)
f[0] = 1
sum_f = 0 # 窗口中的 f[i] 之和
left = 0
for i, x in enumerate(nums):
# 1. 入
sum_f += f[i]
while min_q and x <= nums[min_q[-1]]:
min_q.pop()
min_q.append(i)
while max_q and x >= nums[max_q[-1]]:
max_q.pop()
max_q.append(i)
# 2. 出
while nums[max_q[0]] - nums[min_q[0]] > k:
sum_f -= f[left]
left += 1
if min_q[0] < left:
min_q.popleft()
if max_q[0] < left:
max_q.popleft()
# 3. 更新答案
f[i + 1] = sum_f % MOD
return f[n]
###java
class Solution {
public int countPartitions(int[] nums, int k) {
final int MOD = 1_000_000_007;
int n = nums.length;
Deque<Integer> minQ = new ArrayDeque<>(); // 更快的写法见【Java 数组】
Deque<Integer> maxQ = new ArrayDeque<>();
int[] f = new int[n + 1];
f[0] = 1;
long sumF = 0; // 窗口中的 f[i] 之和
int left = 0;
for (int i = 0; i < n; i++) {
// 1. 入
sumF += f[i];
int x = nums[i];
while (!minQ.isEmpty() && x <= nums[minQ.peekLast()]) {
minQ.pollLast();
}
minQ.addLast(i);
while (!maxQ.isEmpty() && x >= nums[maxQ.peekLast()]) {
maxQ.pollLast();
}
maxQ.addLast(i);
// 2. 出
while (nums[maxQ.peekFirst()] - nums[minQ.peekFirst()] > k) {
sumF -= f[left];
left++;
if (minQ.peekFirst() < left) {
minQ.pollFirst();
}
if (maxQ.peekFirst() < left) {
maxQ.pollFirst();
}
}
// 3. 更新答案
f[i + 1] = (int) (sumF % MOD);
}
return f[n];
}
}
###java
class Solution {
public int countPartitions(int[] nums, int k) {
final int MOD = 1_000_000_007;
int n = nums.length;
int[] minQ = new int[n];
int[] maxQ = new int[n];
int minHead = 0, minTail = -1;
int maxHead = 0, maxTail = -1;
int[] f = new int[n + 1];
f[0] = 1;
long sumF = 0; // 窗口中的 f[i] 之和
int left = 0;
for (int i = 0; i < n; i++) {
// 1. 入
sumF += f[i];
int x = nums[i];
while (minHead <= minTail && x <= nums[minQ[minTail]]) {
minTail--;
}
minQ[++minTail] = i;
while (maxHead <= maxTail && x >= nums[maxQ[maxTail]]) {
maxTail--;
}
maxQ[++maxTail] = i;
// 2. 出
while (nums[maxQ[maxHead]] - nums[minQ[minHead]] > k) {
sumF -= f[left];
left++;
if (minQ[minHead] < left) {
minHead++;
}
if (maxQ[maxHead] < left) {
maxHead++;
}
}
// 3. 更新答案
f[i + 1] = (int) (sumF % MOD);
}
return f[n];
}
}
###cpp
class Solution {
public:
int countPartitions(vector<int>& nums, int k) {
const int MOD = 1'000'000'007;
int n = nums.size();
deque<int> min_q, max_q;
vector<int> f(n + 1);
f[0] = 1;
long long sum_f = 0; // 窗口中的 f[i] 之和
int left = 0;
for (int i = 0; i < n; i++) {
int x = nums[i];
// 1. 入
sum_f += f[i];
while (!min_q.empty() && x <= nums[min_q.back()]) {
min_q.pop_back();
}
min_q.push_back(i);
while (!max_q.empty() && x >= nums[max_q.back()]) {
max_q.pop_back();
}
max_q.push_back(i);
// 2. 出
while (nums[max_q.front()] - nums[min_q.front()] > k) {
sum_f -= f[left];
left++;
if (min_q.front() < left) {
min_q.pop_front();
}
if (max_q.front() < left) {
max_q.pop_front();
}
}
// 3. 更新答案
f[i + 1] = sum_f % MOD;
}
return f[n];
}
};
###go
func countPartitions(nums []int, k int) int {
const mod = 1_000_000_007
n := len(nums)
var minQ, maxQ []int
f := make([]int, n+1)
f[0] = 1
sumF := 0 // 窗口中的 f[i] 之和
left := 0
for i, x := range nums {
// 1. 入
sumF += f[i]
for len(minQ) > 0 && x <= nums[minQ[len(minQ)-1]] {
minQ = minQ[:len(minQ)-1]
}
minQ = append(minQ, i)
for len(maxQ) > 0 && x >= nums[maxQ[len(maxQ)-1]] {
maxQ = maxQ[:len(maxQ)-1]
}
maxQ = append(maxQ, i)
// 2. 出
for nums[maxQ[0]]-nums[minQ[0]] > k {
sumF -= f[left]
left++
if minQ[0] < left {
minQ = minQ[1:]
}
if maxQ[0] < left {
maxQ = maxQ[1:]
}
}
// 3. 更新答案
f[i+1] = sumF % mod
}
return f[n]
}
复杂度分析
- 时间复杂度:$\mathcal{O}(n)$,其中 $n$ 是 $\textit{nums}$ 的长度。每个下标至多入队出队各两次。
- 空间复杂度:$\mathcal{O}(n)$。
相似题目
更多相似题目,见下面动态规划题单的「§5.2 最优划分」和「§11.3 单调队列优化 DP」。
分类题单
- 滑动窗口与双指针(定长/不定长/单序列/双序列/三指针/分组循环)
- 二分算法(二分答案/最小化最大值/最大化最小值/第K小)
- 单调栈(基础/矩形面积/贡献法/最小字典序)
- 网格图(DFS/BFS/综合应用)
- 位运算(基础/性质/拆位/试填/恒等式/思维)
- 图论算法(DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流)
- 动态规划(入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望)
- 常用数据结构(前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树)
- 数学算法(数论/组合/概率期望/博弈/计算几何/随机算法)
- 贪心与思维(基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造)
- 链表、二叉树与回溯(前后指针/快慢指针/DFS/BFS/直径/LCA/一般树)
- 字符串(KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机)
DP & 双指针
解法:DP & 双指针
维护 $f(i)$ 表示前 $i$ 个元素的分割方案。转移时,枚举上一个子段的末尾在哪,有转移方程
$$
f(i) = \sum f(j)
$$
其中 $j$ 满足 $\max(a_{j + 1}, a_{j + 2}, \cdots, a_i) - \min(a_{j + 1}, a_{j + 2}, \cdots, a_i) \le k$
直接计算 DP 方程的复杂度为 $\mathcal{O}(n^2)$,还需要进一步观察合法的 $j$ 有什么特征。
注意到,如果某个子数组的极值之差小于等于 $k$,那么它的子数组的极值之差也小于等于 $k$。这是典型的双指针特征,因此合法的 $j$ 就是一段连续值,从某个值一直取到 $(i - 1)$。用双指针算出最小的合法 $j$,再用前缀和计算区间和即可。复杂度 $\mathcal{O}(n\log n)$,这里的 $\log n$ 主要是我们需要用数据结构(比如 multiset)动态维护滑动窗口里的最小值和最大值。
参考代码(c++)
class Solution {
public:
int countPartitions(vector<int>& nums, int K) {
int n = nums.size();
const int MOD = 1e9 + 7;
// f[i]:前 i 个元素的分割方案数
// g[i]:f 的前缀和
long long f[n + 1], g[n + 1];
f[0] = g[0] = 1;
// 用 multiset 记录滑动窗口里的数,方便求出最小值和最大值
multiset<int> ms;
// 枚举双指针的右端点 i,计算合法子段左端点的最小值 j
for (int i = 1, j = 1; i <= n; i++) {
ms.insert(nums[i - 1]);
while (j < i && *prev(ms.end()) - *ms.begin() > K) {
ms.erase(ms.find(nums[j - 1]));
j++;
}
// j 是最小的左端点
// 那么上一个子段最小的右端点就是 j - 1
// 前缀和就得减去 j - 2 的值
f[i] = (g[i - 1] - (j - 2 >= 0 ? g[j - 2] : 0) + MOD) % MOD;
g[i] = (g[i - 1] + f[i]) % MOD;
}
return f[n];
}
};