题目理解

这是一个有限内存下的括号匹配问题。我们需要在只能存储 $22$ 比特信息（即 $0$ 到 $2^{22}-1$ 的整数）的限制下，判断一个由 <, >, [, ] 组成的字符串是否是合法的括号序列。

合法括号序列的定义：

• 空字符串是合法的
• 如果 $x$ 合法，则 <x> 和 `[x]$ 合法
• 如果 $x$ 和 $y$ 都合法，则 $xy$ 合法

限制条件：

• 每天只能查询一个字符（调用一次 Get）
• 每天结束时只能记住一个 $22$ 比特的整数
• 必须在 $15000$ 天内完成

关键观察

1. 问题本质

这是一个带两种括号类型的括号匹配问题。我们需要检查：

1. 括号是否匹配（开括号和闭括号对应）
2. 括号类型是否正确（< 对应 >，[ 对应 ]）
3. 嵌套顺序是否正确

2. 经典解法（无内存限制）

如果没有内存限制，我们可以用一个栈来解决：

• 遇到开括号 < 或 [ 时压栈
• 遇到闭括号时检查栈顶是否匹配
• 最后栈应为空

3. 有限内存的挑战

由于只能存储 $22$ 比特信息（约 $4$ 百万个状态），而字符串长度可达 $100$，我们无法直接存储整个栈。

关键思路：我们不需要存储整个栈，只需要存储足够的信息来继续匹配过程。

算法设计

1. 状态编码

我们可以将当前的状态编码为：

• 当前栈的摘要信息
• 下一个要查询的位置
• 其他必要的控制信息

由于 $2^{22} = 4194304$，我们需要精心设计状态编码。

2. 栈的压缩表示

对于括号匹配，关键信息是：

• 当前未匹配的开括号序列
• 但我们可以只存储部分摘要信息

一个有效的方法是使用哈希或校验和来表示栈的状态。

3. 状态转移

每天我们：

1. 根据当前状态 $M$ 决定查询位置 $pos$
2. 调用 Get(pos) 获取字符 $c$
3. 根据 $c$ 更新状态
4. 返回新状态或答案

状态编码的优化

为了充分利用 $22$ 比特，我们可以这样编码：

• 位置 pos: 0-99 → 7比特（支持到127）
• 栈深度 depth: 0-100 → 7比特
• 栈哈希 hash: 0-255 → 8比特
• 控制标志: 剩余比特用于特殊状态

总计：7 + 7 + 8 = 22比特

处理边界情况

1. 字符串读完但栈不为空：返回 -2（不合法）
2. 栈空时遇到闭括号：返回 -2（不合法）
3. 类型不匹配：返回 -2（不合法）
4. 栈深度超过限制：返回 -2（不合法）
5. 所有字符处理完且栈为空：返回 -1（合法）

复杂度分析

• 时间复杂度：$O(N)$，每个字符处理一次
• 空间复杂度：$O(1)$，只使用固定大小的状态
• 查询次数：最多 $N$ 次，远小于 $15000$ 的限制

测试策略

由于这是交互题，需要仔细测试：

1. 合法字符串的各种情况
2. 不合法字符串的各种情况
3. 边界情况（空串、最大长度等）
4. 哈希冲突的情况

总结

这道题的关键在于：

1. 理解有限内存的约束：只能存储 $22$ 比特信息
2. 状态压缩：将栈信息编码为哈希值
3. 增量处理：每次只处理一个字符，更新状态
4. 精心设计编码：充分利用可用的比特位

通过将栈的状态压缩为哈希值，我们可以在有限内存下完成括号匹配检查。这种方法虽然理论上可能因哈希冲突而错误，但在实际数据范围内效果很好。