双端队列在算法竞赛里一直是个“工具人”角色——写单调队列要用它做模拟题偶尔也要用它。直到我刷到《算法竞赛进阶指南》里那道经典的“双端队列”题才发现自己以前对这个容器的理解有多浅。那道题表面考数据结构内核却是排序、贪心和一点点组合直觉。这篇文章我打算完整拆一遍从题目模型的还原到为什么一个队列对应一段“单谷”下标序列再到贪心扫描的每个分支最后把我踩过的坑和调试方法都交代清楚。适合算法竞赛选手、准备机试或面试的朋友也适合所有想把“双端队列”从会用变成用透的人。1. 双端队列这道题究竟在考什么1.1 别急着写代码先看破题目的伪装这道题的原始模型可以还原成这样有一个长度为 N 的序列元素会按照给定的顺序逐个到达。每来一个元素你都要决定两件事把它放进哪个双端队列以及插到那个队列的队头还是队尾。所有元素都进队之后要求每个队列从队头到队尾都是不降的并且这些队列按某种顺序首尾相接之后整体也必须是不降的。问最少需要几个这样的双端队列。我第一次读题的时候脑子里全是std::deque的接口想着怎么用容器模拟入队出队。这其实是被“双端队列”四个字带偏了。双端队列只是一个载体题目真正考察的是“入队顺序”和“最终顺序”之间能产生什么样的映射。你不需要真的去维护队列你需要的是找到一种数学模型把问题转化成一个可以用排序和贪心解决的形态。这种“数据结构只是外壳排序才是内核”的题在这本书里很常见。它考察的不是你知道双端队列可以从两头进出而是你能不能把“可以从两头进出”翻译成更抽象的数学条件。翻译成功了代码可能短得惊人翻译不出来想破头也模拟不了。1.2 两个关键假设整体不降、相同值可换位置题目给出的条件里藏着两个极重要的信息。第一个是“这些队列首尾相接后整体不降”。这意味着如果把整个序列里的所有元素按值从小到大排列每个双端队列里含有的元素在排序后的全局序列里一定占据一段连续的位置。两个队列的元素值域不可能交叉一旦交叉拼接后就会在某处出现“大的在前、小的在后”的逆序。这个观察把问题从“若干个队列”变成了“把排序后的序列切成连续的若干段”。第二个是“相同值的元素可以任意交换相对顺序”。因为两个元素值相等时谁排在最终序列的前面都不影响“不降”这个约束。这一步非常关键它给了我们自由调整的余地。实际算法里我们会把相同值的元素合成一个“值块”块内部的下标顺序可以按需要整体翻转。这是后面贪心扫描能成立的前提。站在出题人的角度这两个假设就是整道题的题眼。很多题解上来直接贴代码不提这两句话读者就会觉得“这个贪心为什么对了”其实所有分支判断都是从这两个假设推出来的。1.3 适合怎样的人、带着什么问题来读如果你正在准备算法竞赛这道题值得认真做一遍。它对“排序后重建下标”这种思维方式的训练比刷十道模板题都管用。如果你是在准备面试或者机试这道题也能帮你理解一个道理当题目里的数据规模达到十万级别任何“模拟所有可能入队方案”的思路都是死路必须找到线性或 log 级别的数学建模。读这篇文章之前建议你先把原题自己想一想哪怕只是盯着“双端队列”四个字想十分钟。带着“为什么一个双端队列对应一个先降后升的序列”这个问题来看收获会大很多。如果你已经看过题解但没看懂贪心分支这篇文章的第三章会把你所有“这里为什么这么判”的疑问解决掉。2. 把入队规则翻译成“单谷段”2.1 给每个元素贴一个原始下标现在做第一件事把原序列里的元素全部排序然后给排序后的每个位置贴上它原本在序列里的下标。比如原序列是A [1, 5, 2, 4, 3]排序后变成[1, 2, 3, 4, 5]它们对应的原始下标依次是[1, 3, 5, 4, 2]。这个下标序列就是整个建模的核心载体。为什么只看下标就够了因为值已经排好序了“最终顺序不降”这个要求已经由排序自动满足。剩下的问题是原序列到达顺序和最终顺序之间能不能通过双端队列的入队操作衔接起来。下标记录了每个元素在原序列里的到达先后值排序后的下标序列则记录了“最终排第 k 的元素原来排在第几个到达”。两个序列之间的变化规律就直接对应了双端队列的操作可行性。这一步相当于把问题从“值”的维度完全转化到了“位置”的维度。以后我们讨论的所有“上升”“下降”“转折”指的都是这个下标序列的走势而不是值的大小。2.2 为什么一个队列就是一段“先降后升”接着思考一个具体的双端队列。假设这个队列最终包含 k 个元素它们在全局排序中的名次是一个连续区间。按原序列到达顺序看这 k 个元素各自有一个最终名次把它们按到达顺序写出来得到一个长度为 k 的序列。问题是这个序列满足什么条件时才能用同一个双端队列装下模拟一下双端队列的操作就很清楚了。第一个元素进来只能放在队里。第二个元素进来如果它比队里的元素小就放队头比队里的元素大就放队尾。注意“最终顺序是不降的”这个约束——如果新元素最终名次比当前队头还小它必须成为新的队头如果比当前队尾还大它必须成为新的队尾。也就是说每来一个新元素它的名次要么比之前所有出现过的元素都小要么比之前所有出现过的元素都大。这样一来名次序列只能是这个样子一开始不断变小因为每个新元素都比之前的小被压到队头到达某个最小值之后再不断变大因为每个新元素都比之前的大被加到队尾。先连续下降再连续上升这就是“单谷”。反过来只要名次序列是单谷的我们就能按照“下降段放队头、上升段放队尾”的规则操作一定能构造出这个队列。等价性成立。为什么不能出现“先升后降再升”这种走势因为“升”说明某个元素放到了队尾“降”说明另一个元素放到了队头中间一旦有反复后来出现的比队尾大的元素和比队头小的元素就无法同时保持在最终序列里的正确位置。用一个生活类比想象你手里有一副扑克牌每次只能把新牌放到整叠牌的最上面或最下面最后整叠牌从左到右要是递增的。那么你拿牌的顺序必须先是不断拿小牌放上面再不断拿大牌放下面中间不允许乱跳。很好理解。2.3 用一个小例子验证翻译结果还是用A [1, 5, 2, 4, 3]。排序后贴下标得到[1, 3, 5, 4, 2]。这个序列先升1→3→5后降5→4→2是单峰不是单谷所以不能装进一个队列至少要两个。分成两段试试第一段[1, 3, 5]纯上升单谷第二段[4, 2]纯下降单谷。所以答案是 2。对应到实际队列第一段装的是原序列里下标 1、3、5 的三个元素按到达顺序是 1、2、3依次放队尾即可第二段装下标 2、4 的两个元素按到达顺序是 5 先到、4 后到5 进队后 4 比它小放队头得到[4, 5]。两个队列拼起来是[1, 2, 3, 4, 5]完美符合条件。这个例子虽然简单但它完整演示了一个思想实验先不看值只留下标再判断下标序列能不能切成尽量少的单谷段。题目从“模拟入队操作”变成了“切分段”复杂度和可操作性都完全不同了。3. 贪心扫描分块、排序、维护方向3.1 预处理按值排序并给相同值分块有了“单谷段”这个模型剩下的问题就是给定一个下标序列相同值可重排怎么把它切成最少的单谷段。常规做法是排序然后按值分块。具体实现上把每个元素存成一个二元组(值, 原始下标)先按值升序排序值相同的时候按下标升序排序。排序之后值相同的元素会聚成一段连续区间。对每一个连续的值块我们只需要记录两个东西块内最小下标mn和最大下标mx。因为你决定这个值块在最终排列里按升序还是降序出现时能影响和前后块衔接的只有它开头的下标和末尾的下标中间那些下标不会改变“能不能延续趋势”的判断结果。这里还有一个容易忽略的点既然相同值的内部顺序可以任意调换那么在排序后的全局数组里同一个值块内部的下标可以整体从大到小排列也可以整体从小到大排列。这两种排列方式恰好对应了块在“单谷段”里承担的不同角色。我们后面贪心要做的就是给每个值块选择合适的排列方向。3.2 下降阶段怎么决策用一个变量last记录当前构造的单谷段最后一个元素在最终排列顺序里的原始下标再用一个变量state表示当前段整体的趋势-1代表还没到谷底整体趋势是下降1代表已经过了谷底整体趋势是上升。遍历值块的时候核心问题就是“下一个块怎么摆才能让当前段尽量延续”。先看state -1的情况。当前趋势是下降也就是说上一个块的末尾下标是last我们希望下一个块开头的下标比last小让下降趋势延续下去。比较当前块的mx和last。如果mx last说明整个块的所有下标都比last小那么这个块可以整体放在last的左边完全可以继续下降。为了给后续留出最大的下降空间我们把块按降序排列也就是先排mx最后落到mn然后更新last mn。这样当前段末尾的下标变得更小了趋势不变。反过来如果mx last说明块内至少有一个下标不小于last想让它整体继续下降已经不可能。这时候谷底就落在当前块内或者正好在上一块的末尾。我们把块按升序排列也就是从mn开始一路升到mx段的末尾下标更新为mx同时state切换成上升。这里有个细节即便mn也大于last谷底也只是在last处提前形成块从mn开始上升仍然合理段没有断。3.3 上升阶段怎么决策再看state 1。趋势已经转为上升我们希望下一个块的开头下标比last大让上升趋势继续。比较当前块的mn和last。如果mn last整个块所有下标都比last大上升趋势可以延续。块按升序排列从mn到mx更新last mx。这是最顺利的情况段数不变。如果mn last说明块里存在下标不大于last的元素上升趋势被截断了。当前段必须在这里结束新开一个段。新段从下降开始所以这个块要按降序排列从mx一路降到mn更新last mnstate切回下降同时ans。这里很容易写错成“块按升序排列”一旦排反后面所有判断都会乱掉。总结一下贪心的核心其实只有四句话下降时能继续下降就尽量继续不能就在块内翻身上升时能继续上升就继续不能就立刻开新段翻身。每个分支的选择都是唯一最优的没有“也许按另一种排法更好”的空间。3.4 完整实现代码与复杂度代码量非常短核心扫描不到二十行。下面是我在本地验证过的 C 实现#include bits/stdc.h using namespace std; const int N 200005; struct Node { int val, idx; bool operator (const Node other) const { if (val ! other.val) return val other.val; return idx other.idx; } } a[N]; int main() { int n; scanf(%d, n); for (int i 1; i n; i) { scanf(%d, a[i].val); a[i].idx i; } sort(a 1, a n 1); int ans 1; int last INT_MAX; int state -1; // -1: 下降阶段, 1: 上升阶段 for (int i 1; i n; ) { int j i; while (j n a[j].val a[i].val) j; int mn a[i].idx; int mx a[j - 1].idx; if (state -1) { if (mx last) { last mn; } else { state 1; last mx; } } else { if (mn last) { last mx; } else { ans; state -1; last mn; } } i j; } printf(%d\n, ans); return 0; }排序复杂度是O(N log N)扫描是O(N)总复杂度就是O(N log N)。对十万级的数据毫无压力。整个算法的巧妙之处就在mn和mx的用法上一个值块内部的完整顺序我们根本不需要维护只要知道两端就能判断它和上一个块能不能接上。4. 边界情况、反例与踩坑记录4.1 last 初始化和首块处理的细节我第一次写的时候last初始化的值是0结果第一个块进来就触发了“转上升”的分支整个答案完全错乱。正确做法是把last设成足够大的数比如INT_MAX让第一块必然满足mx last进入下降分支然后把last更新成第一块的mn。为什么要这样设计因为第一块之前没有任何元素按理说它应该成为一个新段的起点。如果一个新段以下降趋势开始对后续是最有利的——将来要么继续下降要么在某个块内翻身转上升。把last设成无穷大就相当于“前面没有限制”强制第一块以降序排列、段尾落在mn让下降趋势从最开始就建立起来。这是一种很典型的“哨兵”技巧在贪心扫描里经常用到。另外注意ans的初始值应该是1而不是0。因为整个下标序列至少能分成一段哪怕只有一个元素答案也是 1。只有在上升阶段被截断、需要新开段的时候才ans。有的同学把初始值设成 0最后所有用例都差 1排查半天才发现是这里的问题。4.2 同值块排序方向为什么不能图省事很多人看完题解会觉得反正同值的可以随便换那我就先按原下标升序排好后面不再管它。这个想法在数据随机时可能碰巧没错但一旦遇到特定数据就会挂。举个例子原序列A [1, 2, 1]。排序后值序列是[1, 1, 2]对应下标如果固定按升序排列得到[1, 3, 2]。这个序列先升后降不是单谷需要 2 个队列。但如果我们把两个 1 的相对顺序换一下得到[3, 1, 2]这是先降后升单谷1 个队列就够了。实际手动模拟也能发现原序列扫描时1 进队2 比 1 大放队尾最后的 1 比队头 1 小或相等放队头最终队列是[1, 1, 2]完全可以一个队列搞定。这个例子说明同值块不是“随便排”而是要参与贪心决策的。块内选择升序还是降序决定了块尾落在mx还是mn这直接影响下一块能不能接上。如果偷懒把同值块固定排序等于丢掉了一半的决策自由度结果自然是错的。4.3 最常见建模错误把方向搞反还有一个高频错误是把“先降后升”记成“先升后降”。我见过不少人在推导的时候想当然最终顺序是升序那原序列扫描过去名次应该也是升序才对为什么是下降这就是没想清楚“名次”和“到达顺序”的关系。再强调一遍这里说的“下降”指的是按原序列到达顺序写出来的最终名次序列。原序列先到的元素在最终排序里可能排得很靠后也可能排得很靠前。先到一个大值、后到一个小值名次序列就是下降的。双端队列允许你不断把后来的小值压到队头于是先到的最大值会一直往队尾方向退这就是“下降段”对应的操作。想检验自己的方向对不对就拿A [2, 1]这种两个元素的小数据模拟一遍。2 先到1 后到1 比 2 小放队头最终[1, 2]一个队列搞定。按原序写名次是[2, 1]下降。所以方向确实是“先降后升”不是反过来。4.4 用对拍验证你的实现这种贪心题最怕的就是“样例过了、随机数据挂了”。我建议写一个暴力程序来对拍。暴力方法不需要模拟双端队列操作既然我们已经证明了问题等价于“切分成最少的单谷段”那就可以直接枚举所有分段方案对每个位置尝试切或不切然后检查每一段的下标序列是否满足先降后升。N 很小的时候这个暴力是能跑完的。对拍脚本的流程是随机生成 N 在 1 到 8 之间的序列分别跑贪心程序和暴力程序比对答案。我实际操作中发现这个对拍能抓出的问题主要有两类一类是state切换时机写错一类是同值块没有考虑mn和mx而直接排序。对拍数据只要跑上几千组正确性就有底了。5. 从这题延伸出去双端队列的其它打开方式5.1 单调队列滑动窗口问题的最佳拍档如果说“双端队列”这道题是拿双端队列当思维模型那滑动窗口最大值才是它最经典的数据结构应用。单调队列用双端队列维护一个“下标递增、值递减”的结构窗口右移时队头如果不是当前窗口内的元素就弹出新元素入队前把所有比它小的元素从队尾弹出。每个元素至多入队一次、出队一次复杂度O(N)。// 滑动窗口最大值a 为原数组k 为窗口大小 dequeint dq; for (int i 1; i n; i) { while (!dq.empty() a[dq.back()] a[i]) dq.pop_back(); dq.push_back(i); if (dq.front() i - k) dq.pop_front(); if (i k) printf(%d\n, a[dq.front()]); }这段代码里deque真正发挥了“队头弹出、队尾插入”的双向能力少一个方向都不行。很多初学者分不清单调队列和优先队列其实就看一点单调队列能维护“窗口”这个概念优先队列不行。5.2 “可翻转块”的思维还能用在哪这道题里最值得带走的东西其实是“把连续的相等元素视作可翻转的块”这个思想。很多区间分段类的问题里都会出现类似的结构某些元素的相对顺序可以自由调整于是我们把它看成一个整体只关心块的两端不关心块内部的完整排列。比如一些环形序列的题拆环成链之后再对链做某种“反转段”的贪心再比如某些括号序列或路径计数问题里“连续段可以整体翻转”能大大压缩状态。这种思路的本质是当约束只关心边界状态时内部细节就是可以丢弃的信息。做题的时候多问自己一句——“这里真的需要知道块内部长什么样吗”答案一出来复杂度往往就降下来了。5.3 推荐练习路径与后续思考方向如果你想彻底吃透这道题我的建议是不要只看题解按这个顺序来先自己手动模拟几个小数据把“单谷”这个概念验证一遍然后不看代码自己写一遍贪心实现最后写一个暴力对拍跑随机数据。完成这三步你对“排序 下标 贪心”这个组合的理解会上一个台阶。还可以接着想一想如果题目改成“最少用几个栈”答案会怎么变栈只能从一端进出自由度比双端队列小很多对应的下标序列条件会苛刻得多。对比这两个变式你能更清楚地看到双端队列“多出来的一端”到底带来了多少灵活性。我在实际刷题和带人的过程中见过太多人卡在这道题的第一道坎——建模。他们总觉得双端队列就该用deque去模拟结果越模拟越乱。后来我总结出一句经验遇到双端队列相关的组合优化题先别想容器先想“最终顺序”和“原始顺序”之间的关系把它变成一段抽象的序列走势。这道题最值钱的就是这个转换过程代码反而是最容易的部分。把这个坎迈过去以后遇到再花哨的变式你都能一眼看到底。 
长河君 · 2026/10/15 17:44:17 · 阅读 1.2k 双端队列从会用到用透：排序贪心建模与单谷序列解析
双端队列在算法竞赛里一直是个“工具人”角色——写单调队列要用它做模拟题偶尔也要用它。直到我刷到《算法竞赛进阶指南》里那道经典的“双端队列”题才发现自己以前对这个容器的理解有多浅。那道题表面考数据结构内核却是排序、贪心和一点点组合直觉。这篇文章我打算完整拆一遍从题目模型的还原到为什么一个队列对应一段“单谷”下标序列再到贪心扫描的每个分支最后把我踩过的坑和调试方法都交代清楚。适合算法竞赛选手、准备机试或面试的朋友也适合所有想把“双端队列”从会用变成用透的人。1. 双端队列这道题究竟在考什么1.1 别急着写代码先看破题目的伪装这道题的原始模型可以还原成这样有一个长度为 N 的序列元素会按照给定的顺序逐个到达。每来一个元素你都要决定两件事把它放进哪个双端队列以及插到那个队列的队头还是队尾。所有元素都进队之后要求每个队列从队头到队尾都是不降的并且这些队列按某种顺序首尾相接之后整体也必须是不降的。问最少需要几个这样的双端队列。我第一次读题的时候脑子里全是std::deque的接口想着怎么用容器模拟入队出队。这其实是被“双端队列”四个字带偏了。双端队列只是一个载体题目真正考察的是“入队顺序”和“最终顺序”之间能产生什么样的映射。你不需要真的去维护队列你需要的是找到一种数学模型把问题转化成一个可以用排序和贪心解决的形态。这种“数据结构只是外壳排序才是内核”的题在这本书里很常见。它考察的不是你知道双端队列可以从两头进出而是你能不能把“可以从两头进出”翻译成更抽象的数学条件。翻译成功了代码可能短得惊人翻译不出来想破头也模拟不了。1.2 两个关键假设整体不降、相同值可换位置题目给出的条件里藏着两个极重要的信息。第一个是“这些队列首尾相接后整体不降”。这意味着如果把整个序列里的所有元素按值从小到大排列每个双端队列里含有的元素在排序后的全局序列里一定占据一段连续的位置。两个队列的元素值域不可能交叉一旦交叉拼接后就会在某处出现“大的在前、小的在后”的逆序。这个观察把问题从“若干个队列”变成了“把排序后的序列切成连续的若干段”。第二个是“相同值的元素可以任意交换相对顺序”。因为两个元素值相等时谁排在最终序列的前面都不影响“不降”这个约束。这一步非常关键它给了我们自由调整的余地。实际算法里我们会把相同值的元素合成一个“值块”块内部的下标顺序可以按需要整体翻转。这是后面贪心扫描能成立的前提。站在出题人的角度这两个假设就是整道题的题眼。很多题解上来直接贴代码不提这两句话读者就会觉得“这个贪心为什么对了”其实所有分支判断都是从这两个假设推出来的。1.3 适合怎样的人、带着什么问题来读如果你正在准备算法竞赛这道题值得认真做一遍。它对“排序后重建下标”这种思维方式的训练比刷十道模板题都管用。如果你是在准备面试或者机试这道题也能帮你理解一个道理当题目里的数据规模达到十万级别任何“模拟所有可能入队方案”的思路都是死路必须找到线性或 log 级别的数学建模。读这篇文章之前建议你先把原题自己想一想哪怕只是盯着“双端队列”四个字想十分钟。带着“为什么一个双端队列对应一个先降后升的序列”这个问题来看收获会大很多。如果你已经看过题解但没看懂贪心分支这篇文章的第三章会把你所有“这里为什么这么判”的疑问解决掉。2. 把入队规则翻译成“单谷段”2.1 给每个元素贴一个原始下标现在做第一件事把原序列里的元素全部排序然后给排序后的每个位置贴上它原本在序列里的下标。比如原序列是A [1, 5, 2, 4, 3]排序后变成[1, 2, 3, 4, 5]它们对应的原始下标依次是[1, 3, 5, 4, 2]。这个下标序列就是整个建模的核心载体。为什么只看下标就够了因为值已经排好序了“最终顺序不降”这个要求已经由排序自动满足。剩下的问题是原序列到达顺序和最终顺序之间能不能通过双端队列的入队操作衔接起来。下标记录了每个元素在原序列里的到达先后值排序后的下标序列则记录了“最终排第 k 的元素原来排在第几个到达”。两个序列之间的变化规律就直接对应了双端队列的操作可行性。这一步相当于把问题从“值”的维度完全转化到了“位置”的维度。以后我们讨论的所有“上升”“下降”“转折”指的都是这个下标序列的走势而不是值的大小。2.2 为什么一个队列就是一段“先降后升”接着思考一个具体的双端队列。假设这个队列最终包含 k 个元素它们在全局排序中的名次是一个连续区间。按原序列到达顺序看这 k 个元素各自有一个最终名次把它们按到达顺序写出来得到一个长度为 k 的序列。问题是这个序列满足什么条件时才能用同一个双端队列装下模拟一下双端队列的操作就很清楚了。第一个元素进来只能放在队里。第二个元素进来如果它比队里的元素小就放队头比队里的元素大就放队尾。注意“最终顺序是不降的”这个约束——如果新元素最终名次比当前队头还小它必须成为新的队头如果比当前队尾还大它必须成为新的队尾。也就是说每来一个新元素它的名次要么比之前所有出现过的元素都小要么比之前所有出现过的元素都大。这样一来名次序列只能是这个样子一开始不断变小因为每个新元素都比之前的小被压到队头到达某个最小值之后再不断变大因为每个新元素都比之前的大被加到队尾。先连续下降再连续上升这就是“单谷”。反过来只要名次序列是单谷的我们就能按照“下降段放队头、上升段放队尾”的规则操作一定能构造出这个队列。等价性成立。为什么不能出现“先升后降再升”这种走势因为“升”说明某个元素放到了队尾“降”说明另一个元素放到了队头中间一旦有反复后来出现的比队尾大的元素和比队头小的元素就无法同时保持在最终序列里的正确位置。用一个生活类比想象你手里有一副扑克牌每次只能把新牌放到整叠牌的最上面或最下面最后整叠牌从左到右要是递增的。那么你拿牌的顺序必须先是不断拿小牌放上面再不断拿大牌放下面中间不允许乱跳。很好理解。2.3 用一个小例子验证翻译结果还是用A [1, 5, 2, 4, 3]。排序后贴下标得到[1, 3, 5, 4, 2]。这个序列先升1→3→5后降5→4→2是单峰不是单谷所以不能装进一个队列至少要两个。分成两段试试第一段[1, 3, 5]纯上升单谷第二段[4, 2]纯下降单谷。所以答案是 2。对应到实际队列第一段装的是原序列里下标 1、3、5 的三个元素按到达顺序是 1、2、3依次放队尾即可第二段装下标 2、4 的两个元素按到达顺序是 5 先到、4 后到5 进队后 4 比它小放队头得到[4, 5]。两个队列拼起来是[1, 2, 3, 4, 5]完美符合条件。这个例子虽然简单但它完整演示了一个思想实验先不看值只留下标再判断下标序列能不能切成尽量少的单谷段。题目从“模拟入队操作”变成了“切分段”复杂度和可操作性都完全不同了。3. 贪心扫描分块、排序、维护方向3.1 预处理按值排序并给相同值分块有了“单谷段”这个模型剩下的问题就是给定一个下标序列相同值可重排怎么把它切成最少的单谷段。常规做法是排序然后按值分块。具体实现上把每个元素存成一个二元组(值, 原始下标)先按值升序排序值相同的时候按下标升序排序。排序之后值相同的元素会聚成一段连续区间。对每一个连续的值块我们只需要记录两个东西块内最小下标mn和最大下标mx。因为你决定这个值块在最终排列里按升序还是降序出现时能影响和前后块衔接的只有它开头的下标和末尾的下标中间那些下标不会改变“能不能延续趋势”的判断结果。这里还有一个容易忽略的点既然相同值的内部顺序可以任意调换那么在排序后的全局数组里同一个值块内部的下标可以整体从大到小排列也可以整体从小到大排列。这两种排列方式恰好对应了块在“单谷段”里承担的不同角色。我们后面贪心要做的就是给每个值块选择合适的排列方向。3.2 下降阶段怎么决策用一个变量last记录当前构造的单谷段最后一个元素在最终排列顺序里的原始下标再用一个变量state表示当前段整体的趋势-1代表还没到谷底整体趋势是下降1代表已经过了谷底整体趋势是上升。遍历值块的时候核心问题就是“下一个块怎么摆才能让当前段尽量延续”。先看state -1的情况。当前趋势是下降也就是说上一个块的末尾下标是last我们希望下一个块开头的下标比last小让下降趋势延续下去。比较当前块的mx和last。如果mx last说明整个块的所有下标都比last小那么这个块可以整体放在last的左边完全可以继续下降。为了给后续留出最大的下降空间我们把块按降序排列也就是先排mx最后落到mn然后更新last mn。这样当前段末尾的下标变得更小了趋势不变。反过来如果mx last说明块内至少有一个下标不小于last想让它整体继续下降已经不可能。这时候谷底就落在当前块内或者正好在上一块的末尾。我们把块按升序排列也就是从mn开始一路升到mx段的末尾下标更新为mx同时state切换成上升。这里有个细节即便mn也大于last谷底也只是在last处提前形成块从mn开始上升仍然合理段没有断。3.3 上升阶段怎么决策再看state 1。趋势已经转为上升我们希望下一个块的开头下标比last大让上升趋势继续。比较当前块的mn和last。如果mn last整个块所有下标都比last大上升趋势可以延续。块按升序排列从mn到mx更新last mx。这是最顺利的情况段数不变。如果mn last说明块里存在下标不大于last的元素上升趋势被截断了。当前段必须在这里结束新开一个段。新段从下降开始所以这个块要按降序排列从mx一路降到mn更新last mnstate切回下降同时ans。这里很容易写错成“块按升序排列”一旦排反后面所有判断都会乱掉。总结一下贪心的核心其实只有四句话下降时能继续下降就尽量继续不能就在块内翻身上升时能继续上升就继续不能就立刻开新段翻身。每个分支的选择都是唯一最优的没有“也许按另一种排法更好”的空间。3.4 完整实现代码与复杂度代码量非常短核心扫描不到二十行。下面是我在本地验证过的 C 实现#include bits/stdc.h using namespace std; const int N 200005; struct Node { int val, idx; bool operator (const Node other) const { if (val ! other.val) return val other.val; return idx other.idx; } } a[N]; int main() { int n; scanf(%d, n); for (int i 1; i n; i) { scanf(%d, a[i].val); a[i].idx i; } sort(a 1, a n 1); int ans 1; int last INT_MAX; int state -1; // -1: 下降阶段, 1: 上升阶段 for (int i 1; i n; ) { int j i; while (j n a[j].val a[i].val) j; int mn a[i].idx; int mx a[j - 1].idx; if (state -1) { if (mx last) { last mn; } else { state 1; last mx; } } else { if (mn last) { last mx; } else { ans; state -1; last mn; } } i j; } printf(%d\n, ans); return 0; }排序复杂度是O(N log N)扫描是O(N)总复杂度就是O(N log N)。对十万级的数据毫无压力。整个算法的巧妙之处就在mn和mx的用法上一个值块内部的完整顺序我们根本不需要维护只要知道两端就能判断它和上一个块能不能接上。4. 边界情况、反例与踩坑记录4.1 last 初始化和首块处理的细节我第一次写的时候last初始化的值是0结果第一个块进来就触发了“转上升”的分支整个答案完全错乱。正确做法是把last设成足够大的数比如INT_MAX让第一块必然满足mx last进入下降分支然后把last更新成第一块的mn。为什么要这样设计因为第一块之前没有任何元素按理说它应该成为一个新段的起点。如果一个新段以下降趋势开始对后续是最有利的——将来要么继续下降要么在某个块内翻身转上升。把last设成无穷大就相当于“前面没有限制”强制第一块以降序排列、段尾落在mn让下降趋势从最开始就建立起来。这是一种很典型的“哨兵”技巧在贪心扫描里经常用到。另外注意ans的初始值应该是1而不是0。因为整个下标序列至少能分成一段哪怕只有一个元素答案也是 1。只有在上升阶段被截断、需要新开段的时候才ans。有的同学把初始值设成 0最后所有用例都差 1排查半天才发现是这里的问题。4.2 同值块排序方向为什么不能图省事很多人看完题解会觉得反正同值的可以随便换那我就先按原下标升序排好后面不再管它。这个想法在数据随机时可能碰巧没错但一旦遇到特定数据就会挂。举个例子原序列A [1, 2, 1]。排序后值序列是[1, 1, 2]对应下标如果固定按升序排列得到[1, 3, 2]。这个序列先升后降不是单谷需要 2 个队列。但如果我们把两个 1 的相对顺序换一下得到[3, 1, 2]这是先降后升单谷1 个队列就够了。实际手动模拟也能发现原序列扫描时1 进队2 比 1 大放队尾最后的 1 比队头 1 小或相等放队头最终队列是[1, 1, 2]完全可以一个队列搞定。这个例子说明同值块不是“随便排”而是要参与贪心决策的。块内选择升序还是降序决定了块尾落在mx还是mn这直接影响下一块能不能接上。如果偷懒把同值块固定排序等于丢掉了一半的决策自由度结果自然是错的。4.3 最常见建模错误把方向搞反还有一个高频错误是把“先降后升”记成“先升后降”。我见过不少人在推导的时候想当然最终顺序是升序那原序列扫描过去名次应该也是升序才对为什么是下降这就是没想清楚“名次”和“到达顺序”的关系。再强调一遍这里说的“下降”指的是按原序列到达顺序写出来的最终名次序列。原序列先到的元素在最终排序里可能排得很靠后也可能排得很靠前。先到一个大值、后到一个小值名次序列就是下降的。双端队列允许你不断把后来的小值压到队头于是先到的最大值会一直往队尾方向退这就是“下降段”对应的操作。想检验自己的方向对不对就拿A [2, 1]这种两个元素的小数据模拟一遍。2 先到1 后到1 比 2 小放队头最终[1, 2]一个队列搞定。按原序写名次是[2, 1]下降。所以方向确实是“先降后升”不是反过来。4.4 用对拍验证你的实现这种贪心题最怕的就是“样例过了、随机数据挂了”。我建议写一个暴力程序来对拍。暴力方法不需要模拟双端队列操作既然我们已经证明了问题等价于“切分成最少的单谷段”那就可以直接枚举所有分段方案对每个位置尝试切或不切然后检查每一段的下标序列是否满足先降后升。N 很小的时候这个暴力是能跑完的。对拍脚本的流程是随机生成 N 在 1 到 8 之间的序列分别跑贪心程序和暴力程序比对答案。我实际操作中发现这个对拍能抓出的问题主要有两类一类是state切换时机写错一类是同值块没有考虑mn和mx而直接排序。对拍数据只要跑上几千组正确性就有底了。5. 从这题延伸出去双端队列的其它打开方式5.1 单调队列滑动窗口问题的最佳拍档如果说“双端队列”这道题是拿双端队列当思维模型那滑动窗口最大值才是它最经典的数据结构应用。单调队列用双端队列维护一个“下标递增、值递减”的结构窗口右移时队头如果不是当前窗口内的元素就弹出新元素入队前把所有比它小的元素从队尾弹出。每个元素至多入队一次、出队一次复杂度O(N)。// 滑动窗口最大值a 为原数组k 为窗口大小 dequeint dq; for (int i 1; i n; i) { while (!dq.empty() a[dq.back()] a[i]) dq.pop_back(); dq.push_back(i); if (dq.front() i - k) dq.pop_front(); if (i k) printf(%d\n, a[dq.front()]); }这段代码里deque真正发挥了“队头弹出、队尾插入”的双向能力少一个方向都不行。很多初学者分不清单调队列和优先队列其实就看一点单调队列能维护“窗口”这个概念优先队列不行。5.2 “可翻转块”的思维还能用在哪这道题里最值得带走的东西其实是“把连续的相等元素视作可翻转的块”这个思想。很多区间分段类的问题里都会出现类似的结构某些元素的相对顺序可以自由调整于是我们把它看成一个整体只关心块的两端不关心块内部的完整排列。比如一些环形序列的题拆环成链之后再对链做某种“反转段”的贪心再比如某些括号序列或路径计数问题里“连续段可以整体翻转”能大大压缩状态。这种思路的本质是当约束只关心边界状态时内部细节就是可以丢弃的信息。做题的时候多问自己一句——“这里真的需要知道块内部长什么样吗”答案一出来复杂度往往就降下来了。5.3 推荐练习路径与后续思考方向如果你想彻底吃透这道题我的建议是不要只看题解按这个顺序来先自己手动模拟几个小数据把“单谷”这个概念验证一遍然后不看代码自己写一遍贪心实现最后写一个暴力对拍跑随机数据。完成这三步你对“排序 下标 贪心”这个组合的理解会上一个台阶。还可以接着想一想如果题目改成“最少用几个栈”答案会怎么变栈只能从一端进出自由度比双端队列小很多对应的下标序列条件会苛刻得多。对比这两个变式你能更清楚地看到双端队列“多出来的一端”到底带来了多少灵活性。我在实际刷题和带人的过程中见过太多人卡在这道题的第一道坎——建模。他们总觉得双端队列就该用deque去模拟结果越模拟越乱。后来我总结出一句经验遇到双端队列相关的组合优化题先别想容器先想“最终顺序”和“原始顺序”之间的关系把它变成一段抽象的序列走势。这道题最值钱的就是这个转换过程代码反而是最容易的部分。把这个坎迈过去以后遇到再花哨的变式你都能一眼看到底。