华为笔试 10.14：股票交易模拟、数独求解与 BST 后序遍历

《面试题目》

1. 股票交易模拟：有 n 个卖家和 m 个买家，各自给出价格和数量。依次处理买家，每次选择报价不高于买家价格且最接近的卖家，尽量成交。成交后，其余符合价格条件的卖家报价增加 x。重复交易，直到买够或无人符合条件，求总成交金额。
2. 数独求解：给定一个 n×n 的数独，n 为完全平方数，0 表示空格。填入 1 到 n，使每行、每列及每个 √n×√n 的宫内数字不重复，已有数字不能修改。给出一个解；无解或者有多个解则输出 0。
3. 二叉搜索树验证：给定一个整数数组，判断它能否作为某棵二叉搜索树的后序遍历序列。若不能，输出 -1；若能，求该树每一层最右侧节点的值之和。

《参考解析》

第一题：交易模拟要先把规则抠成可执行的步骤

这类模拟题丢分几乎都来自「规则理解偏差」而不是算法难度（候选人自评这题只拿到 37%）。做题前必须把题干逐句翻译成可执行流程，并列出所有不确定点：价格相同的卖家怎么选（先来后到还是任意）、卖家报价增加 x 是「每次成交后立即全体加」还是「每轮结束加一次」、加了之后同一个买家是否还用新价格继续匹配、买家数量不足时是部分成交还是跳过、以及没有符合条件卖家时是结束整个流程还是继续下一个买家。用最小例子手工推演一遍（两三个买卖家、两轮成交）来验证自己的理解，是这类题的保命步骤。

实现上建议用有序结构维护卖家报价：因为要「找不高于买家价格且最接近」的卖家，用按价格排序的容器（TreeMap、有序数组、或价格分桶）配合数量余量；每次成交要扣减卖家的剩余数量（卖完移除），并对「其余符合价格条件的卖家」批量加价——批量加价用「懒标记 + 全局偏移」能避免每次 O(n) 遍历（记录一个全局加法量，取出的价格再加上偏移即可，但要注意只有符合价格条件的那些卖家才加，这可能需要按价格区间打标记或用差分思想）。总成交金额按「成交单价 × 成交数量」累加（注意单价是成交那一刻的价格）。数据范围要看清：n、m 与价格上界决定是否需要用 long、以及排序与批量操作的复杂度是否会超时。写完之后用自己推演的小例子做一次对拍，比空想更可靠。

第二题：数独求解（要判断唯一解）

这题比标准数独多一个条件——必须判断「是否有多解」，多解也要输出 0。做法是回溯（DFS）：按行优先或「最少候选格优先」的顺序找空格，尝试填入 1 到 n 的合法值（用行、列、宫三个集合/位掩码做快速合法性判断），递归下去；找到第一个解之后不能直接返回，要继续搜索直到找到第二个解或搜索结束——找到第二个解就直接输出 0 并终止。用位掩码（每行、每列、每宫的已用数字用整数表示，1 << v）能让合法性判断与回溯的撤销都是 O(1)，n 较小时速度足够。边界与细节：n 是完全平方数（4、9、16），宫的大小是 √n；输入本身就可能非法（已有数字重复），这种情况直接无解输出 0；递归深度是空格数量，注意栈深度；如果用「最少候选优先」的启发式排序，能显著减少搜索树规模。判定多解时的剪枝要注意：一旦确认第二个解就立刻返回，避免做无谓的完整搜索（因为题目只要求区分「唯一解」与「零解/多解」）。

第三题：BST 后序遍历序列的验证与逐层最右节点求和

合法性与求值是两问，要分开处理。验证思路利用 BST 后序的性质：序列的最后一个元素是根；从前往后找到第一个大于根的位置，该位置之前是左子树（都小于根）、之后到根之前是右子树（都必须大于根）；若右子树区间内存在小于根的值则非法。递归地对左右子树重复这一判断。这个做法可以写成 O(n²) 的朴素递归，也能用「单调栈 + 上下界」优化到 O(n)：遍历序列时用栈维护右子树路径，遇到更小的值就弹栈并更新下界，任何时刻值必须落在 (下界, 上界) 内。要注意允许重复值与否的问题——如果允许重复（左子树 ≤ 根），判断条件要相应放宽，题目没有说明时要按常规假设（严格 BST）并在心里记下这个假设。

求「每一层最右侧节点的值之和」需要先把序列还原成树的结构：用上面的划分递归建树（或者用栈直接建），然后层序遍历（BFS）取每层的最后一个节点累加。要在实现时注意边界：空数组（输出 0）、只有一个节点、退化成链的情况（递归深度可能达到 n，O(n²) 的递归建树会退化，这时用栈的 O(n) 做法更稳）。三题的共同经验是：华为笔试的时间很紧，先把规则与边界写清楚、用小例子验证，再动手；卡住超过十几分钟就先去拿下一题的分，自评里这题 100% 而第一题 37%，正说明「理解规则」比「写出算法」更容易丢分。