今天我们通过一道非常经典的“幕布覆盖”问题彻底剖析双指针滑动的两种思维“定左探右”以及“定右缩左”的标准滑动骨架并给出两套满分模板。一、 题目描述【题目大意】在一张网格图中每一列有且仅有一个格子被小蜗涂了色现在给你每一列被涂色的格子的高度 ai。 现在有一块高度为 h 的长方形幕布挂在高度 x 的时候能盖住的高度区间为 [x−h1,x]可以在列方向延伸宽度可以是任意值。 问你固定高度后一块布最多可以覆盖住连续的多少列的格子【输入格式】第一行给出两个数代表列数 n 和高度 h。 接下来一行给出每一列被涂色的格子高度 a[i]。【样例输入】7 4 1 4 5 3 6 1 4【样例输出】4【数据范围】1≤n≤1000001≤h,a[i]≤10^6。二、 题目分析与核心不等式这道题的物理外衣是“幕布覆盖”我们需要翻译成纯粹的数学语言。 幕布挂在高度x时覆盖的最低点是x−h1。 这意味着在幕布能盖住的任意一段连续区间内最高点与最低点的差值最大只能是h−1。 换句话说对于区间[l,r]合法的条件是max(a[l…r])−min(a[l…r])h注题目规定高度差加1不大于幕布高度即极差≤h−1等价于极差h。题目要求我们找到满足合法条件的最长连续区间长度。为了实现O(N)的降维打击我们需要结合滑动窗口双指针与单调队列。三、 解法一定左探右这是很多初学者的第一直觉固定左端点i让右端点侦察兵j往未来探索。 易错点这种写法极易导致“试探未来污染队列”和“漏算末尾元素”。 方案我们必须利用C 的||短路特性并在循环内外打上极其严密的逻辑补丁。核心算法设计每次i更新时新的一天先把队列里i的过期老将清理掉。侦察兵j不断往右试探。循环条件必须是极其精妙的jn(ji||a[maq]-a[miq] h)。jn保证最后一个元素有机会结账。ji是空队列保护机制当队列因左指针推进被清空时利用||短路特性直接放行防止后续求极差时越界。先结账后入队每次进入循环先结算mamax(ma, j-i1)确认合法后再执行入队操作彻底杜绝“假账”。黄金刹车片结账后j会自增若jn必须立刻break防止后续入队越界。解法一完整代码//覆盖 //求出每个区间最大值和最小值 //最大值和最小值之差1不大于幕布高度即可 #include iostream using namespace std; int n,h; int a[1000010];//每一列被涂色的格子的高度 int miq[1000010];//记录最小高度的队列 int maq[1000010];//记录最大高度的队列 int mif1,mir0;//最小高度队首队尾 int maf1,mar0;//最大高度队首队尾 int ma;//最多可以覆盖多少列格子 int main(){ ios::sync_with_stdio(false); cin.tie(0); cinnh; for(int i1;in;i) cina[i]; int j0;//幕布右端 for(int i1;in;i){//遍历幕布左端 //当队列非空且队首过期 就把队首清除 while(mifmirmiq[mif]i) mif; while(mafmarmaq[maf]i) maf; //当幕布右端不超过边界(幕布右端未超过幕布左端且最高点-最低点差值要小于h //否则幕布盖不过来 while(jn(ji||a[maq[maf]]-a[miq[mif]]h)){ //每一轮开始时统计最大格子列数 mamax(ma,j-i1); j; //防止最后一轮j越界然后访问a[j] if(jn) break; //当最小高度队列非空且幕布右端高度小于等于队尾时 //队尾出队 while(mifmira[j]a[miq[mir]]){ mir--; } //j入队 miq[mir]j; //当最大高度队列非空且幕布右端高度大于等于队尾时 //队尾出队 while(mafmara[j]a[maq[mar]]){ mar--; } //j入队 maq[mar]j; } } coutma; return 0; }四、 解法二定右缩左相比于第一种防御性编程竞赛中更推崇的标程写法是转换视角“只处理当下绝不试探未来”。核心算法设计让右边界r像推土机一样每天无脑往前走新元素无条件入队。每次入队后回头查账。如果发现极差≥h超标了我们就强迫左边界l往前收缩。收缩时把下标l的过期老将踢出。终极防爆边界循环收缩的前提加上lr。当l追上r时区间仅剩一个元素极差为0绝对合法。这一步强行刹车保证队列永远不为空彻底斩断越界风险。存活出审查循环的 [l,r] 绝对合法每日结算一次。解法二完整代码//覆盖 第二种做法 //固定右端点移动左端点 #include iostream using namespace std; int n,h; int a[1000010];//每一列被涂色的格子的高度 int miq[1000010];//记录最小高度的队列 int maq[1000010];//记录最大高度的队列 int mif1,mir0;//最小高度队首队尾 int maf1,mar0;//最大高度队首队尾 int ma;//最多可以覆盖多少列格子 int main(){ ios::sync_with_stdio(false); cin.tie(0); cinnh; for(int i1;in;i) cina[i]; int l1;//左端 for(int r1;rn;r){//遍历右端 //当最小高度队列非空且右端点高度小于等于最小高度队尾时 //队尾出队 while(mifmira[r]a[miq[mir]]){ mir--; } //右端点入队 miq[mir]r; //当最大高度队列非空且右端点高度大于等于最大高度队尾时 //队尾出队 while(mafmara[r]a[maq[mar]]){ mar--; } //右端点入队 maq[mar]r; //l不超过边界且判断接下来检查最大高度-最小高度如果大于等于h //代表幕布不能完全盖住就把幕布左端往右锁 while(lra[maq[maf]]-a[miq[mif]]h){ //如果不小于h就把l往右移动 l; //当队列非空且队首过期时 //就清理过期的 while(mifmirmiq[mif]l) mif; while(mafmarmaq[maf]l) maf; } //接下来肯定是符合要求的 mamax(ma,r-l1); } coutma; return 0; }五、 时空复杂度与易错点总结时间复杂度O(N)。两个解法中每个元素最多入队一次、出队一次。均摊下来是严格的线性时间。空间复杂度O(N)。需要开辟原数组和两个单调队列。避坑指南队列里永远只存下标。绝不存具体的值否则清理过期元素时无法对比位置。警惕-1和1数组如果是1-indexed左边界l必须从 1 开始。如果从0开始答案会永远比正确结果多 1。的短路求值判空条件如mifmir必须放在逻辑与的最前面利用短路特性充当安全带。
滑动窗口与双调队列：幕布覆盖问题（定右缩左满分板子）改编自LeetCode 1438
今天我们通过一道非常经典的“幕布覆盖”问题彻底剖析双指针滑动的两种思维“定左探右”以及“定右缩左”的标准滑动骨架并给出两套满分模板。一、 题目描述【题目大意】在一张网格图中每一列有且仅有一个格子被小蜗涂了色现在给你每一列被涂色的格子的高度 ai。 现在有一块高度为 h 的长方形幕布挂在高度 x 的时候能盖住的高度区间为 [x−h1,x]可以在列方向延伸宽度可以是任意值。 问你固定高度后一块布最多可以覆盖住连续的多少列的格子【输入格式】第一行给出两个数代表列数 n 和高度 h。 接下来一行给出每一列被涂色的格子高度 a[i]。【样例输入】7 4 1 4 5 3 6 1 4【样例输出】4【数据范围】1≤n≤1000001≤h,a[i]≤10^6。二、 题目分析与核心不等式这道题的物理外衣是“幕布覆盖”我们需要翻译成纯粹的数学语言。 幕布挂在高度x时覆盖的最低点是x−h1。 这意味着在幕布能盖住的任意一段连续区间内最高点与最低点的差值最大只能是h−1。 换句话说对于区间[l,r]合法的条件是max(a[l…r])−min(a[l…r])h注题目规定高度差加1不大于幕布高度即极差≤h−1等价于极差h。题目要求我们找到满足合法条件的最长连续区间长度。为了实现O(N)的降维打击我们需要结合滑动窗口双指针与单调队列。三、 解法一定左探右这是很多初学者的第一直觉固定左端点i让右端点侦察兵j往未来探索。 易错点这种写法极易导致“试探未来污染队列”和“漏算末尾元素”。 方案我们必须利用C 的||短路特性并在循环内外打上极其严密的逻辑补丁。核心算法设计每次i更新时新的一天先把队列里i的过期老将清理掉。侦察兵j不断往右试探。循环条件必须是极其精妙的jn(ji||a[maq]-a[miq] h)。jn保证最后一个元素有机会结账。ji是空队列保护机制当队列因左指针推进被清空时利用||短路特性直接放行防止后续求极差时越界。先结账后入队每次进入循环先结算mamax(ma, j-i1)确认合法后再执行入队操作彻底杜绝“假账”。黄金刹车片结账后j会自增若jn必须立刻break防止后续入队越界。解法一完整代码//覆盖 //求出每个区间最大值和最小值 //最大值和最小值之差1不大于幕布高度即可 #include iostream using namespace std; int n,h; int a[1000010];//每一列被涂色的格子的高度 int miq[1000010];//记录最小高度的队列 int maq[1000010];//记录最大高度的队列 int mif1,mir0;//最小高度队首队尾 int maf1,mar0;//最大高度队首队尾 int ma;//最多可以覆盖多少列格子 int main(){ ios::sync_with_stdio(false); cin.tie(0); cinnh; for(int i1;in;i) cina[i]; int j0;//幕布右端 for(int i1;in;i){//遍历幕布左端 //当队列非空且队首过期 就把队首清除 while(mifmirmiq[mif]i) mif; while(mafmarmaq[maf]i) maf; //当幕布右端不超过边界(幕布右端未超过幕布左端且最高点-最低点差值要小于h //否则幕布盖不过来 while(jn(ji||a[maq[maf]]-a[miq[mif]]h)){ //每一轮开始时统计最大格子列数 mamax(ma,j-i1); j; //防止最后一轮j越界然后访问a[j] if(jn) break; //当最小高度队列非空且幕布右端高度小于等于队尾时 //队尾出队 while(mifmira[j]a[miq[mir]]){ mir--; } //j入队 miq[mir]j; //当最大高度队列非空且幕布右端高度大于等于队尾时 //队尾出队 while(mafmara[j]a[maq[mar]]){ mar--; } //j入队 maq[mar]j; } } coutma; return 0; }四、 解法二定右缩左相比于第一种防御性编程竞赛中更推崇的标程写法是转换视角“只处理当下绝不试探未来”。核心算法设计让右边界r像推土机一样每天无脑往前走新元素无条件入队。每次入队后回头查账。如果发现极差≥h超标了我们就强迫左边界l往前收缩。收缩时把下标l的过期老将踢出。终极防爆边界循环收缩的前提加上lr。当l追上r时区间仅剩一个元素极差为0绝对合法。这一步强行刹车保证队列永远不为空彻底斩断越界风险。存活出审查循环的 [l,r] 绝对合法每日结算一次。解法二完整代码//覆盖 第二种做法 //固定右端点移动左端点 #include iostream using namespace std; int n,h; int a[1000010];//每一列被涂色的格子的高度 int miq[1000010];//记录最小高度的队列 int maq[1000010];//记录最大高度的队列 int mif1,mir0;//最小高度队首队尾 int maf1,mar0;//最大高度队首队尾 int ma;//最多可以覆盖多少列格子 int main(){ ios::sync_with_stdio(false); cin.tie(0); cinnh; for(int i1;in;i) cina[i]; int l1;//左端 for(int r1;rn;r){//遍历右端 //当最小高度队列非空且右端点高度小于等于最小高度队尾时 //队尾出队 while(mifmira[r]a[miq[mir]]){ mir--; } //右端点入队 miq[mir]r; //当最大高度队列非空且右端点高度大于等于最大高度队尾时 //队尾出队 while(mafmara[r]a[maq[mar]]){ mar--; } //右端点入队 maq[mar]r; //l不超过边界且判断接下来检查最大高度-最小高度如果大于等于h //代表幕布不能完全盖住就把幕布左端往右锁 while(lra[maq[maf]]-a[miq[mif]]h){ //如果不小于h就把l往右移动 l; //当队列非空且队首过期时 //就清理过期的 while(mifmirmiq[mif]l) mif; while(mafmarmaq[maf]l) maf; } //接下来肯定是符合要求的 mamax(ma,r-l1); } coutma; return 0; }五、 时空复杂度与易错点总结时间复杂度O(N)。两个解法中每个元素最多入队一次、出队一次。均摊下来是严格的线性时间。空间复杂度O(N)。需要开辟原数组和两个单调队列。避坑指南队列里永远只存下标。绝不存具体的值否则清理过期元素时无法对比位置。警惕-1和1数组如果是1-indexed左边界l必须从 1 开始。如果从0开始答案会永远比正确结果多 1。的短路求值判空条件如mifmir必须放在逻辑与的最前面利用短路特性充当安全带。
