Databricks RLE 与 Bit-Packing 混合压缩：8 值分组的可编码性边界

题目重点：拆解连续 8 个重复值才可 RLE、Bit-Packing 固定 8 值块的分段与逆向解析，指出题目未明确尾块格式。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

先用非负整数抽象分段说明：RLE 段是 ≥8 个连续相等值，BP 段恰为连续 8 个值。真实输入含负数与 INT_MIN/MAX，实际有符号映射、整数宽度、最大 run、header/tag、endianness 和尾块格式未给，不能直接套非负 bit width 公式。
将“能否分段”与“如何写 bytes”分开；如果真实题允许不足 8 的尾块或原样 literal，必须由面试官明确。

先证明可编码性：从位置 i 可以选一个长度至少 8 的同值 run，或取恰好 8 值 BP 段。用 reach[i] 表示前 i 个值能否按规则无重叠覆盖，转移时保持原顺序；若要最小字节数，用 dp[i] 最优成本并保存父指针。
若 RLE 允许任意长度 ≥8，同值段长度 L 可以切成一个或多个 RLE，也可与 BP 交错；贪心总选最长 run 不一定最小，因为 header 大小与后续对齐影响总成本。必须先确定每段成本再优化。
BP 的具体打包需要值域/bit width：非负段最大值 M 的最少位宽可为 ceil(log2(M+1))；负数及 INT_MIN/MAX 还需确认 ZigZag、二补码固定位宽或别的映射，以及 b 如何存。Decode 作为 iterator 必须逐段解析 tag/长度、检查剩余 bit 与值域，并按需产出下一个整数。
逐个输入 int 的 encoder 可能要保留候选 run 与 8 值缓冲，直到后续输入或 finish 才能决定分段；如果要求全局最小长度，有限缓冲能否在线决策还取决于成本函数。
若规范要求所有输入都能编码，`[1,2,3]` 是反例：既不够 8 值 BP，也无 8 个同值 RLE。必须补 literal/尾块/padding 等规则之一；在未澄清前，完整 encode/decode 代码会凭空发明格式。

`[5×9, 1,2,3,4,5,6,7,8]` 可抽象分为一个长度 9 的 RLE 和一个 8 值 BP；`[1,2,3]` 在可见两种规则下不可编码。若 BP tag 占 1 byte、RLE tag+count 占 2 byte，才可能比较两种分段的压缩成本；题目未明确这些开销。

长度 N。单纯可达分段用朴素 DP 枚举同值 run 长度可能 O(N²) 时间、O(N) 空间；按 run 端点与成本结构可优化。固定 8 值 BP 转移为 O(1)。Decode 至少 O(N) 输出时间；字节/bit 复杂度依未公开格式。