"去掉外层括号"、"括号得分"等括号类题目与单调栈有什么关联？
括号类题目常需要维护"当前嵌套深度"或"最近未匹配的括号位置"，这可以用栈（或等价于单调栈的思路）来记录。例如"最长有效括号"用栈记录未匹配的左括号下标，遇到右括号时弹出并计算跨度；"括号得分"用栈记录当前分数。这类题的共同点是：栈自动维护了一个"待匹配左括号"的单调序列，栈内元素的位置顺序与深度一致，从而能用栈顶与当前下标差计算最长合法子串或区间。
括号匹配本身是"栈"的经典应用，而"最长合法括号""去除最外层括号"等需要求"区间长度/相互包含关系"时，栈底到栈顶的深度天然单调，与单调栈"维护单调区间"的思想相通。理解"栈维护未匹配左括号的位置，右括号弹出时结算区间"即可。
单调队列处理"窗口最小值"时，为什么只需把比较符号反向？
单调队列维护窗口最值的核心是"队首是最值，队内单调"。求窗口最大值时，维护队首到队尾递减的队列，新元素从队尾弹出所有比它小的元素；求窗口最小值时，只需把比较方向反过来——维护队首到队尾递增的队列，新元素从队尾弹出所有比它大的元素。两种情形算法结构完全一样，只是弹出条件（> vs <）不同，因此"只需把比较符号反向"。
这是因为单调队列的"单调性"方向完全由"最值"的取向决定：要最大就单调递减（队首最大），要最小就单调递增（队首最小）。元素淘汰原则"新元素能替换掉所有不如它优的旧元素"不变，只是"优"的定义（更大/更小）变了。所以只需翻转比较符号，无需改动其他逻辑。
单调队列（deque）如何用 O(1) 均摊操作维护滑动窗口最大值的查询（LeetCode 239）？
维护一个双端队列，存下标，且从队首到队尾下标对应的值严格递减（队首是当前窗口最大值）。每次滑入新元素时：1) 从队尾弹出所有值小于等于新元素的下标（它们不可能再成为最大值，因新元素更晚且更大）；2) 把新下标压入队尾；3) 若队首下标已滑出窗口（< i-k+1），从队首弹出；4) 队首即当前窗口最大值。每个元素最多进出队列一次，总操作 O(n)，每次查询 O(1)。
关键点有两个：一是"单调递减保证队首最大"，二是"只保留窗口内下标、超出窗口的队首淘汰"。因为新元素值更大时，队内所有比它小的旧元素都失去了成为最大值的资格（它们更早滑出且更小），所以被弹出。队首出窗只发生在窗口右移时。这样数据结构既维护了最值又维护了位置合法性。
int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] res = new int[n - k + 1];
Deque<Integer> dq = new ArrayDeque<>(); // 存下标，值递减
int ri = 0;
for (int i = 0; i < n; i++) {
while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();
dq.offerLast(i);
if (dq.peekFirst() <= i - k) dq.pollFirst(); // 出窗
if (i >= k - 1) res[ri++] = nums[dq.peekFirst()];
}
return res;
}
用多重集合（multi-set）/平衡树做滑动窗口最值与单调队列相比，复杂度有何差异？
平衡树（如 TreeMap 的 value 计数）可以在每次插入删除 O(log k) 维护窗口，查询最值 O(1)（取首/尾），处理带窗口的 n 个元素总复杂度 O(n log k)。单调队列则利用"只关心最值、不关心完整有序集合"的特点，用 O(1) 均摊完成插入删除，总复杂度 O(n)。当窗口内还需要"中位数"等需要完整有序信息时，平衡树/双堆更合适；当只需最值时单调队列更快更省空间。
单调队列能 O(1) 是因为它只维护"最值"这一信息，规律性很强（新元素能淘汰所有不如它的）。而平衡树要维护完整有序集合（支持任意元素的查找、删除、中位数），代价是 O(log k)。这就是"信息需求决定复杂度"的体现：只要最值用单调队列，要完整统计用平衡树。
如何用单调栈在 O(n) 时间内构建笛卡尔树（Cartesian Tree）？为何说总复杂度是 O(n)？
构建小根笛卡尔树时，按顺序扫描数组，维护一个栈（即当前树的右链，栈底到栈顶递增）。对每个新节点 x：从栈顶开始，把栈中所有值大于 x 的节点依次弹出（它们成为 x 的左子树），弹出的最后一个节点作为 x 的左孩子；然后 x 成为新栈顶（原栈顶作为 x 的父节点，即把 x 插到右链上）。因为每个节点最多被弹出一次、压入一次，总操作 O(n)，故构建总复杂度 O(n)。这正体现了"右链单调性 + 每个元素只进出一次"的摊还性质。
核心是"右链"（从根一路向右的路径）用单调栈维护。新节点 x 沿右链上爬，把比 x 大的节点全弹出成为 x 的左子树，x 就接在右链上。弹出的节点不会再参与，所以每个节点只进出一次，总 O(n)。这比递归找最大值（O(n log n) 或 O(n) 但常数大）更简洁可证明。
// 小根笛卡尔树构建（返回节点数组，只需维护左右孩子）
int[] left = new int[n], right = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
int last = -1;
while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
last = stack.pop();
}
left[i] = last; // 弹出的最后一个成为左孩子
if (!stack.isEmpty()) right[stack.peek()] = i; // 挂到右链
stack.push(i);
}
如何用单调队列优化"最大子数组和（限长窗口）"这类动态规划？
这类题常见形式是"求长度不超过 K 的最大子数组和"。用前缀和表示，子数组[i..j]的和 = prefix[j] - prefix[i-1]，对每个 j 要找范围 [j-K, j-1] 内最小的 prefix，使和最大。用单调队列维护"区间内值递增的前缀和下标"，队首是范围内的最小前缀和，这样每个 j 都能 O(1) 得到最优的前缀和，整体 O(n)。这本质是用单调队列优化了"固定范围最值查询"的 DP 转移。
把"求和"化为"前缀和之差"后，问题转化为"滑动窗口内找最小前缀和"，正好是单调队列的用武之地。DP 转移方程里需要"窗口内最值"，用单调队列把每个状态的转移从 O(K) 降到 O(1)，从而总复杂度 O(n)。这是单调队列优化 DP 的经典范式。
如何用滑动窗口在 O(n) 时间内求出"最多含 K 个不同字符的最长子串"？
用双指针维护一个窗口，同时用频率表（HashMap 或数组）记录窗口内每个字符的计数，以及一个变量 distinct 记录当前不同字符数。右指针不断右扩加入字符，当 distinct > K 时，左指针右缩并减少对应字符计数，直到 distinct 回到 K。过程中记录窗口最大长度。由于每个字符最多被加入和移除一次，整体 O(n)。
这是"窗口内不同字符数"这一约束的可变长滑动窗口。右扩使窗口"变合法或越界"，左缩只在 distinct 超限时进行，从而保证窗口始终满足"不同字符 ≤ K"。用 distinct 计数配合频率表，避免每次扫描窗口，实现 O(1) 更新，整体 O(n)。
int lengthOfLongestSubstringKDistinct(String s, int k) {
int[] cnt = new int[128];
int distinct = 0, l = 0, ans = 0;
for (int r = 0; r < s.length(); r++) {
if (cnt[s.charAt(r)]++ == 0) distinct++;
while (distinct > k) {
if (--cnt[s.charAt(l)] == 0) distinct--;
l++;
}
ans = Math.max(ans, r - l + 1);
}
return ans;
}
如何证明基于单调栈的贪心策略（如移除 K 位数字、拼接序列）不会错过最优解？
这类贪心通常用"交换论证"或"反证法"证明。核心是证明"贪心选择的局部最优（如删除当前最靠前的逆序对）与某个全局最优解一致，且替换不会变差"。例如移除 K 位数字：当出现降序对（前>后）时，删除前面的数字必然使结果更小（因为高位数字对结果影响最大），所以删除它是最优的局部决策；反复应用该规则，得到的结果不劣于任何其他方案。通过"任意最优解都能被贪心调整到不劣"来证明贪心不遗漏最优。
证明单调栈贪心正确性的通用思路是"最优解可被贪心逐步调整得到"：若贪心在某一步未按最优做，则存在一个交换/替换使结果更优或等价，矛盾。对"移 K 位"类题，关键在于"高位数字的权重最大"，删除高位的降序元素必然最优。一旦证明局部最优蕴含全局最优，贪心即正确，这是"贪心选择性质 + 最优子结构"的体现。
在滑动窗口最大值问题中，如何保证单调队列队首始终是当前窗口内的最大元素？
通过两条规则保证不变量：1) 入队时从队尾弹出所有值小于等于新元素的下标，再把新元素压入队尾——这保证队内从队首到队尾值严格递减，因此队首是队内最大值；2) 每次窗口右移后（或每次查询前），若队首下标已滑出窗口范围（< i-k+1），则从队首将其弹出。因为新元素更大时会淘汰所有更小的旧元素，而旧元素出窗时又从队首移除，所以队首始终是"仍在窗口内且值最大"的元素。
不变量是"队首 = 窗口内最大值的下标"。值递减保证队首是当前队列最大值；出窗淘汰保证队首下标仍在窗口内。两者结合，"队首是窗口内最大"这一性质在每次滑动后都成立。这是单调队列最核心的维护逻辑。
笛卡尔树与 RMQ ±1 问题有什么关系？为何笛卡尔树的中序遍历对应原数组、LCA 对应 RMQ，从而把 RMQ 归约为 LCA？
对数组构建的笛卡尔树，其中序遍历恰好就是原数组顺序（因为构建时按序插入，左子树都来自更早、右子树来自更晚）。同时，任意区间 [l, r] 的最小值，正是笛卡尔树中节点 l 和节点 r 的最近公共祖先（LCA）所对应的值：因为 LCA 是区间内最小的元素，其左右子树分别覆盖区间内位于它两侧的元素。因此 RMQ(l,r) = LCA(l, r) 的值，从而把 RMQ 归约为 LCA 问题。
这是"RMQ 与 LCA 等价"的经典结论。笛卡尔树的根是全局最小值，递归地左右子树是左右区间的最小值，所以任意两个位置 l、r 的 LCA 就是区间 [l,r] 的最小值。而 LCA 可以高效求解（如 ±1 RMQ 的线性构造），因此 RMQ 也能达到 O(1) 查询。这个归约把两个看似无关的问题统一起来。
笛卡尔树在"最大二叉树"（LeetCode 654）中的直接应用是什么？递归找最大值与单调栈 O(n) 有何对比？
LeetCode 654 的最大二叉树定义是"以区间最大值作为根，左半段递归建左子树，右半段递归建右子树"，这恰好就是大根笛卡尔树的定义。因此题目要构建的树本质上就是大根笛卡尔树。递归找最大值每次 O(区间)+O(递归) 平均 O(n log n)、最坏 O(n²)（有序数组）；用单调栈维护右链构建笛卡尔树则稳定 O(n)，是最优解。所以标准解法是单调栈 O(n) 建树。
识别出"最大二叉树 = 大根笛卡尔树"是解题的关键。递归区间找最大值是朴素做法，但最坏 O(n²)；单调栈维护右链，每个节点只进出一次，O(n)。这也解释了为什么单调栈能构建笛卡尔树——它正是"区间最大值递归建树"的线性等价实现。
在面试中，如何向面试官展示从暴力 O(n²) 解法推导到单调栈 O(n) 解法的思考过程？
推荐的推导路径是：先给出暴力思路（对每个元素向左/右扫描找边界，O(n²)），指出瓶颈在于"重复扫描"；然后发现关键观察——"每个元素的前一个/下一个更大更小信息可以通过一次扫描得到"，且"被更大的元素淘汰的元素无需再被后续元素考虑"，从而引出单调栈"每个元素只进出一次"的线性性质；最后展示栈的维护规则并给出 O(n) 代码。这样既体现复杂度分析能力，又展示模式识别与优化能力。
面试官看重的是"从暴力出发逐步优化"的思维过程，而非直接背出单调栈。关键是点出暴力的瓶颈（重复比较）和单调栈的优化来源（淘汰机制 + 每个元素只进出一次）。先写暴力、再优化、再证明，是数据结构面试的标准范式。
为什么单调队列在固定窗口下，每个元素也最多进出一次？
每个元素在滑动窗口移动过程中，只会被压入队尾一次（右指针经过它时），也只会被弹出一次（要么在入队时因被更大的新元素淘汰从队尾弹出，要么在窗口右移、队首出窗时从队首弹出）。由于每个元素只入队一次、出队一次，总操作次数为 O(n)，均摊到每个元素 O(1)。这正是单调队列在固定窗口下能 O(n) 处理 n 个元素的原因。
与单调栈的摊还分析一样，关键是"每个元素只进出一次"这个不变量。入队时的大元素淘汰、出窗时的队首淘汰，都保证每个元素至多被删除一次。因此虽然每次操作可能弹出多个元素，总弹出次数 ≤ n，整体 O(n)。
为什么单调队列存的是候选下标而非值，并在出窗时淘汰？
单调队列存下标而非值，是因为需要判断"是否已滑出窗口"：队首元素即使值最大，一旦下标 < 当前窗口左边界 i-k+1，就必须从队首弹出。只有存下标才能判断位置是否还在窗口内。而出窗淘汰（从队首弹出超窗下标）保证了队列中始终只保留"仍在窗口内"的候选，与"值递减保证队首最大"共同维持不变量。所以下标是判断位置合法性的必需信息。
值只提供"大小关系"，下标提供"位置关系"。窗口最值需要同时约束"最大"和"在窗口内"，因此必须存下标并且在出窗时检查淘汰。若只存值，无法知道该元素是否已滑出窗口，也就无法正确维护最值。
单调栈与哈希表结合，如何记录每个值首次/末次出现等综合信息？
单调栈负责"大小关系与位置关系"，哈希表负责"值到位置的映射"或"值首次/末次出现的下标"。两者结合常用于：先扫描一遍用哈希记录每个值首次(st)和末次(en)出现的下标，然后对每个值用单调栈确定其区间左右边界，或以"末次出现"作为"需移除"的判据。例如移除 K 位数字、或"每个元素扩展到覆盖其所有出现位置"的题，可先用哈希得到每个值的最后出现位置，配合单调栈贪心。
哈希表补充了单调栈不知道的"全局出现信息"（如某值最后出现在哪），单调栈补充了"区间边界/单调关系"。把两者结合，能同时处理"值层面的约束"和"位置层面的单调性"，是不少中难题的常见组合。
在动态窗口（右指针扩展、左指针收缩）场景下，单调队列还成立吗？
成立。单调队列对"窗口两端都移动"依然有效，只要左指针在某次收缩时，把队首中下标小于新左边界（左指针）的元素从队首弹出即可。右指针扩展时仍按"值递减"规则从队尾入队。因为单调队列只要求"查询窗口内最值"，而窗口边界变化都能通过"队首弹出出窗元素"和"队尾淘汰更小元素"来维护，所以无论是固定窗口还是变长动态窗口，单调队列都能适用。
单调队列适用于"窗口连续移动"的场景，只要新元素从右端加入、旧元素从左端移除（无论是否固定长度），就能用同一套维护规则。变长窗口时，左指针收缩是把队首所有小于左边界的下标弹出。因此单调队列在动态窗口下依然成立，只是"出窗"的判定由左指针位置决定。
拼接最大数（LeetCode 321）如何把"从数组中选 k 个数字"这一子问题化为单调栈？
拼接最大数要求从两个数组中按顺序取数字拼成最大数。核心子问题是"从单个数组中按顺序选 i 个数字，使得到的数列最大"——这可以用单调栈贪心：从左往右扫描，当栈顶小于当前数字且还有剩余可删的余地时，弹出栈顶，最终保留恰好 i 个。这个子问题就是"单调栈去除较少的逆序对"。然后枚举从数组 A 取 i 个、数组 B 取 k-i 个的组合，合并两个结果序列（按字典序取较大者）并取最大值。
"从数组中选 k 个保持相对顺序的最大子序列"是经典单调栈子问题，等价于"移除 n-k 个数字使剩余最大"（即 402 的变体）。遍历所有切分 (i, k-i) 后，用归并合并两个子序列（每次取字典序大的一端），得到该切分的结果，再取全局最大。这样把复杂问题分解为单调栈 + 归并 + 枚举。
滑动窗口在"子数组满足某条件"的通用判定框架是什么？
通用框架是：右指针不断扩展窗口（加入新元素），维护窗口内的状态（如频率、和、计数）；当窗口不满足条件时，左指针收缩（移除元素）直到窗口重新满足条件；在每次满足条件的窗口处记录答案（可能是最长、最短或计数）。关键是把"满足某条件"抽象成一个可用的判定函数（如合法(窗口)），并保证右扩左缩时的状态增量更新 O(1)。这个框架适用于"不同字符数≤K"、"和≥target"、"无重复"等各类约束。
滑动窗口的核心是"窗口连续、左右指针单调移动"以及"状态可以增量维护"。先定义"合法条件"，再写死模板（右扩、不合法则左缩、记录），就能处理大多数"子数组满足条件"问题。抽象出"合法判定函数"让框架可复用。
如何用单调栈求"能看到右侧的人"或"可见建筑"的计数问题？
"能看到右侧的人"类问题（如团队竞技、看到的人数）通常用从右往左扫描 + 单调递减栈。对每个位置 i，从右边第一个元素开始，能看到的建筑是"严格递增的可见序列"：因为一旦某个建筑比后面所有建筑都高，就遮挡了更后面的建筑。用单调栈维护"右侧严格递增的可见序列"，新位置 i 弹出栈中所有小于等于当前高度的元素（它们被当前更高的建筑遮挡），栈中剩余元素就是 i 能看到的。计数时还要考虑同高度遮挡等细节。
可见性问题的本质是"高度遮挡"：从 i 往右看，能看到的建筑高度是严格递增的（每个被看到的都高于前一个）。维护一个单调递减栈（从右往左），栈中元素是"右侧可见的严格递增序列"，弹出被遮挡的元素即可。这可用单调栈 O(n) 求解。
移除 K 位数字（LeetCode 402）中，贪心 + 单调递增栈的构造正确性如何保证？
目标是使剩余数字最小。从左往右扫描，维护一个单调递增栈：当当前数字小于栈顶且还有剩余删除次数时，弹出栈顶（因为删除"高位较大的数字"收益最大——高位数字对数值影响最大，删除一个降序对中的首位会使结果变小）。这样每次删除都选择"当前最优"的降序对首位，保证最终结果最小。扫描结束后若还有删除次数，从末尾删（末尾数字最大，删除影响最小）。最后去除前导零。
正确性基于"高位数字的权重大于低位"：出现降序对（前>后）时删除前一位必然使结果变小，且这是局部最优；反复应用直到删除完 K 位，得到的结果不劣于任何其他方案。因为任意一个最优解都可通过"删除高位降序对"得到，故贪心正确。单调递增栈只是高效实现"删除较高位"的机制。
为什么说笛卡尔树与单调栈是"对偶"的？单调栈的弹出序列为何恰好是笛卡尔树右链的逆序？
构建笛卡尔树时用单调栈维护右链（栈底到栈顶递增），每个新节点把栈中比它大的节点弹出，弹出的节点成为其左子树。而单调栈的弹出序列（从栈顶到栈底）恰好对应"被弹出的节点在右链上的顺序"。具体地，右链自底向上是"值递增"的，而单调栈弹出的顺序是"从栈顶到栈底"即从右链上端到下端，因此弹出序列正是右链的逆序。这体现了"单调栈维护右链"与"笛卡尔树结构"的一致性——两者描述的其实是同一棵树。
对偶性体现在：单调栈的"栈内元素"就是笛卡尔树的"当前右链"，栈的 push/pop 操作对应右链的"加入/弹出（成为左子树）"。因此，只要能实现单调栈的维护，就等价于构建了笛卡尔树。这也是为什么能用单调栈 O(n) 建笛卡尔树——它们共享同一套操作。
如何使用"恰好 vs 至少"的翻转技巧：用 atMost(k) - atMost(k-1) 求"恰好 k 个"？
当"恰好 k 个"难以直接统计时，可以转而统计"最多 k 个"（atMost(k)），因为"恰好 k 个" = "最多 k 个" - "最多 k-1 个"。例如"恰好 K 个不同字符的子串数" = atMost(K) - atMost(K-1)。而"最多 k 个"用滑动窗口很容易统计（右扩计数，distinct 超 k 时左缩），复杂度 O(n)。这个翻转把"恰好"的离散边界条件转化为两个"最多"的连续单调条件，大大简化。
这是容斥原理的运用。"恰好 k"与"最多 k"的关系如差集：数量恰好为 k 的集合 = 数量 ≤ k 的集合 - 数量 ≤ k-1 的集合。滑动窗口自然地统计"最多"（因为窗口总能保证满足 ≤ 约束），而"恰好"需要精确定位，不便于滑动窗口。这个翻转技巧是子数组计数问题的经典范式。
Fischer-Heun 结构如何利用 ±1 RMQ 实现 O(n) 预处理、O(1) 查询？它如何用笛卡尔树编码块内、用 Sparse Table 处理块间？
Fischer-Heun 结构把数组分成若干小块的 ±1 RMQ（相邻元素差为 ±1）。对每一块，用"块内相对最小值的笛卡尔树形态"编码成唯一的整数 ID（因为 ±1 的特殊性，块内形状可压缩），从而把块内查询 O(1) 解决；块间（跨块）的最小值用 Sparse Table 预处理，每次查询取两端的块内部分 + 中间的块间最小值，即可 O(1) 得到整个区间最小值。预处理总时间 O(n)。
关键在于"±1 的重要性"：相邻差 ±1 时，块内笛卡尔树形态种类有限，可编码成一个整数，从而块内查询 O(1) 且预处理只需 O(n)。块间用 Sparse Table O(n log n) 预处理，但经优化也能 O(n)。这一结构把 RMQ 的预处理降到 O(n)、查询降到 O(1)，是理论最优的静态 RMQ 方案。
如何用笛卡尔树统一视角看待直方图最大矩形与接雨水？笛卡尔树根=区间最小值、左右子树=左右子区间、矩形面积=高度×子树宽度？
对直方图构建小根笛卡尔树，根是区间最小值，其左右子树对应左右子区间。这意味着：以某个高度为水平线的矩形，其最大宽度恰好是该高度在笛卡尔树中对应节点的子树宽度（左右子树覆盖的长度）。最大矩形就是"高度 × 子树宽度"的最大值。接雨水同样可以看作"在笛卡尔树中，每个节点处的蓄水由左右子树中更高墙决定"。用笛卡尔树能把"找区间最小值/边界"统一为"找子树根"，从而统一理解两类问题。
小根笛卡尔树的根是最小值，递归性质使每个节点的子树正好对应"以该值为最小值的最大区间"。最大矩形中"以某柱为高能扩展的宽度"就是该柱在笛卡尔树中的子树宽度；接雨水中的"夹住水位的左右墙"也对应树中祖先。这个统一视角让两者在结构上同源，都是"区间最小值 + 子树范围"的组合。
Treap 与笛卡尔树为何等价？Treap 的（key 满足 BST、priority 满足 heap）双性质为何恰好对应笛卡尔树的（中序=key 序、堆=priority）？
Treap = Tree + Heap，每个节点有 key（满足 BST，中序遍历有序）和 priority（满足堆性质，父节点 priority 大于子节点）。笛卡尔树同样由二元组 (key, priority) 定义：按 key 中序遍历有序（即 BST 性质），按 priority 满足堆性质。因此 Treap 与笛卡尔树是同一个结构的两种叫法——Treap 强调"作为平衡 BST 的随机化用途"，笛卡尔树强调"由数组（key）与优先级（priority）构造的堆结构"。两者完全等价。
关键是对应：笛卡尔树按数组顺序（key 下标）中序 = 原数组，恰好对应 BST 的中序遍历；而 priority 的堆性质对应 Treap 的堆性质。若给定 key 为数组下标、priority 为数组值，则小根笛卡尔树就是 priority 为堆的 Treap。因此 Treap 的"随机优先级"决定了它的树形，而笛卡尔树就是"用数组值当优先级"的特殊 Treap。
变长窗口（如"和 ≥ target 的最短子数组"）如何用双端（左右指针）推进解决？
用左右指针维护窗口。右指针不断右扩（加入元素，累加和），当窗口和 ≥ target 时，说明当前窗口合法，记录长度并尝试左指针右缩（减去元素）以寻找更短窗口，直到窗口和 < target 再继续右扩。这样每次右扩至少有一步，每个位置进出一次，整体 O(n)，得到满足条件的最短子数组长度。
因所有元素非负，窗口和关于窗口长度单调，所以"和 ≥ target"是单调合法条件，适合滑动窗口。右扩保证找到合法窗口，左缩在合法前提下缩短窗口以逼近最短。"右扩触发合法、左缩优化长度"是变长最短窗口的通用模式。
哈希表维护窗口字符频率时，增删与计数同步有哪些细节需要注意？
右指针加入字符时：频率加 1，若从 0 变为 1 则"不同字符数"加 1。左指针移除字符时：频率减 1，若从 1 变为 0 则"不同字符数"减 1（并可从哈希表中删除该键）。同步的要点是"只有跨越 0↔1 边界才改变 distinct 计数"，以及修正某个字符计数时同时更新它对应的贡献。若用数组计数，则用 cnt[char]==0/1 判断。这样保证 distinct 与 cnt 始终一致。
常见错误是只更新 cnt 忘更新 distinct，或删除键时未同步 distinct。严格遵循"频率跨 0↔1 才改 distinct"的规则，并用 cnt 判断是否需要增减 distinct，能保证窗口状态的一致性和 O(1) 更新。
定长窗口（如"长度为 k 的子数组最大和"）的模板与滑入滑出操作是什么？
定长窗口模板：先构建初始窗口（前 k 个元素）并记录状态；然后枚举 i 从 k 到 n-1，每次"滑入"新元素 nums[i]、"滑出"旧元素 nums[i-k]，用 O(1) 增量更新窗口状态（如和、频率），并记录答案。由于窗口长度固定，左右指针同步移动，无需判定合法性。以"最大和"为例，维护一个 sum，滑入加、滑出减，取最大值。
定长窗口的关键是"固定长度、同步滑入滑出"。不需要 while 收缩，只需每次移动一个位置并增量更新。模板简洁，适用于"长度为 k 的最大/最小和"、"固定长度子串判定"等。
int maxSumFixedK(int[] nums, int k) {
int sum = 0;
for (int i = 0; i < k; i++) sum += nums[i];
int ans = sum;
for (int i = k; i < nums.length; i++) {
sum += nums[i] - nums[i - k]; // 滑入 + 滑出
ans = Math.max(ans, sum);
}
return ans;
}
如何统计以某元素为最小值的子数组个数（容斥/计数型）？
对每个元素 a[i]，用单调栈求出它左边第一个更小元素的位置 L 和右边第一个更小元素的位置 R，则 [L+1, R-1] 是 a[i] 为最小值的最大区间。以 a[i] 为最小值的子数组个数 = (i - L) × (R - i)（左边可选 L+1..i 共 i-L 种起点，右边可选 i..R-1 共 R-i 种终点），相乘即得。对每个元素求和，即可统计所有"以某元素为最小值"的子数组（若要求严格最小，需处理相等元素的边界去重）。
关键是用单调栈一次求出每个元素左右第一个更小元素，然后"左端点可选数 × 右端点可选数"就是该元素作为最小值的子数组个数。这是容斥计数与单调栈结合的经典题。注意相等元素时需约定"左闭右开"等规则避免重复计数。
笛卡尔树在"区间最值查询"中如何应用？为何构建笛卡尔树后 RMQ(l,r) = LCA(位置 l, 位置 r) 的值？
对数组构建笛卡尔树后，任意区间 [l, r] 的最小值（RMQ）等于位置 l 与位置 r 对应节点的最近公共祖先（LCA）的值。因为笛卡尔树的根是全局最小值，其左右子树分别对应根的左右区间，而 l 和 r 的 LCA 正是"区间 [l,r] 内最小元素"所在节点。因此，只要能高效求 LCA，就能 O(1) 或 O(log n) 回答 RMQ 查询。
这是"RMQ 归约为 LCA"的核心应用。笛卡尔树的结构保证：任意两个位置 l、r 的 LCA 是它们在区间 [l,r] 内的最小值。通过预处理 LCA（如 RMQ 的 ±1 化、倍增或 Tarjan），可将 RMQ 查询降到 O(1)。因此构建笛卡尔树 + 求 LCA 是区间最值查询的经典方案。
给定互异数组，小根笛卡尔树是否唯一？若存在重复值该如何处理？
给定互异数组，小根笛卡尔树是唯一的。因为结构完全由"中序=数组序 + 根=区间最小值"递归决定，没有歧义。但当存在重复值时，由于"最小值"不唯一，树不再唯一——需要附加规则（如规定相等的元素谁在左、谁在右）。常见做法是引入稳定次序（如规定下标更小的作为"更小"，或规定相等时右边的作为左子树），把"比较"改为"严格小于/大于等于"来打破平局，从而恢复唯一性。
唯一性来自"每个区间的最小值唯一"这一前提。重复值时用额外规则打破平局（例如把相等元素视为"右侧更大"或"左侧更小"），使每个区间的最小值重新唯一。这个约定也影响单调栈构建时弹出条件（严格 < 还是 ≤）。
为什么变长滑动窗口中右指针只进不退、左指针仅按需收缩？
变长窗口依赖"单调合法条件"：随着窗口扩大，条件容易满足（合法）；随着窗口缩小，条件容易破坏。因此右指针只需不断右扩（扩大窗口、尝试达到合法），左指针只在"窗口不合法（超限）"时按需收缩（缩小窗口、恢复合法）。因为右指针指向的元素一旦被加入不会再被移除（除非左指针扫过），右指针单调前进；左指针也只是单调前进。这样每个元素进出一次，整体 O(n)。
右指针"只进不退"是因为窗口的右端是连续扩展的，不需要回退；左指针"只缩不扩"是因为左端只在需要时前进收缩。若右指针会回退，就退化为暴力了。这是滑动窗口保证 O(n) 的关键——两个指针都单调移动。
窗口合法性判定函数如何抽象，以便应对多种约束（如不同字符数、频率、和）？
把"窗口是否合法"抽象成一个独立的判定函数（如 isLegal(window)），由滑动窗口框架调用：右扩后若非法则左收缩，直到合法。判定函数内部根据约束实现不同逻辑（如 distinct ≤ K、所有频率 ≤ 阈值、和 ≥ target 等），并维护所需的辅助状态。这样把"滑动窗口过程"与"具体约束"解耦，同一套框架可复用，只需替换判定函数和状态维护。
抽象出"合法判定"后，滑动窗口代码可复用，只需注入不同的判定逻辑。常见的做法是维护一个状态对象（频率表、和、计数等），判定函数基于状态判断。这是提高代码可复用性与可测试性的好实践，也让"多约束"问题（如"长度≥L 且不同字符≤K"）能组合判定。