- 正确答案：使用双端单调队列（Monotonic Deque）配合普通链表/数组实现支持 O(1) add、O(1) delete（尾删或指定位置删需额外结构）、O(1) getMax 的自定义 list；但若要求任意位置 delete 且仍维持 O(1) getMax，则必须引入「双栈 + 辅助单调栈」或「双向链表 + 哈希表 + 最大堆延迟删除」结构；而针对“数据量十几万”且强调效率与工程可行性的场景，最优解是：底层用 ArrayList（动态数组）存储元素，同时维护一个单调递减双端队列（Deque）作为 max 窗口缓存，并配合一个哈希表记录每个值的出现频次（用于支持带重复元素的删除），从而实现： - add(value): O(1) 均摊（deque 尾部弹出小元素后入队） - delete(value): O(1) 均摊（哈希表计数减一，若为 deque 首元素且计数归零则惰性清理首部） - getMax(): O(1) 直接取 deque 首元素 - 解答思路：首先明确需求本质：这是一个支持动态增删 + 实时查询全局最大值的数据结构，不是静态数组，也不是滑动窗口——而是类似“可删堆”的在线操作。朴素方案如每次 getmax 都遍历 O(n) 显然不可接受（十几万 × 多次查询 → 百万级比较，超时）。接着排除错误路径： • 单纯用 PriorityQueue（堆）：add 和 getMax 是 O(log n)，但标准堆不支持 O(log n) 删除任意元素（除非用懒删除 + HashMap 记录已删状态，此时 delete 接口需传入 value 或 node 引用）；而 Java 的 PriorityQueue 没有 remove(Object) 的 O(log n) 实现（实际是 O(n) 查找 + O(log n) 调整），C++ std::priority_queue 根本不支持任意删。 • 用 TreeSet（红黑树）：add/remove/getMax（last()）都是 O(log n)，总时间复杂度 O(k log n)，k 为操作总数，十几万操作约 1.7e6 次比较，可接受，但不符合“O(1) getmax”隐含期望（面试官常期待更优解）。 • 正确突破口在于：getMax 要 O(1)，必须缓存当前最大值；但删除可能删掉最大值，所以不能只记一个值，而要维护一个“候选最大值序列”，且能快速淘汰失效项 → 这正是单调队列的核心思想。进一步，因删除是按值而非按位置（如 remove(5) 表示删一个值为 5 的元素），需支持重复元素和多次删除同一值 → 必须引入频次映射（HashMap countMap）实现延迟清除。 - 深度知识讲解：【底层数据结构协同原理】该结构由三部分组成： 1. 主存储：ArrayList data —— 提供 O(1) 尾插、O(1) 尾删（若只支持尾删），但若要求任意值删除（如 remove(int val)），则需配合哈希表定位（但无法 O(1) 定位所有下标，故改用频次管理，放弃下标追踪，转为逻辑删除）。 2. 单调双端队列：Deque maxDeq —— 维护一个严格递减序列（从头到尾：max, next_max, ...），保证队首永远是当前有效最大值。入队规则：从队尾开始，弹出所有 ≤ 当前 value 的元素（因它们后续不可能成为最大值），再压入 value；出队仅发生在 getmax 后发现队首已失效时（惰性清理）。 3. 频次哈希表：HashMap counts —— 记录每个值当前在 data 中剩余多少个。当调用 delete(val) 时，counts.put(val, counts.getOrDefault(val, 0) - 1)；随后在 getmax 前检查：while (!maxDeq.isEmpty() && counts.getOrDefault(maxDeq.peekFirst(), 0) == 0) maxDeq.pollFirst(); 【时间复杂度证明】 - add(value)：deque 尾部最多被每个元素访问一次（均摊），故 O(1) 均摊。 - delete(value)：仅更新哈希表 O(1)，无即时 deque 操作。 - getmax()：惰性清理最坏 O(n)，但每个元素至多进出 deque 一次 → 总操作代价 O(n)，均摊 O(1)。【边界与鲁棒性】 • 空容器调用 getmax：应抛异常或返回 Optional.empty()。 • 删除不存在的值：counts 可能为 null 或 0，需判空，不报错（静默忽略或 throw NoSuchElementException 视接口定义而定）。 • 重复最大值：如 [5,3,5]，maxDeq = [5,5]（非严格递减亦可，但推荐严格递减 + 频次配合，更清晰）。【对比其他方案】 • 双栈法（MaxStack）：适用于 LIFO 场景（只允许栈式增删），不满足 list 的任意删需求。 • 平衡二叉搜索树（TreeSet）：支持 O(log n) 全操作，代码简洁，但常数大，且无法达到 O(1) getmax，面试中若被追问“能否更好”，即需引出单调队列方案。 • 分块思想（sqrt decomposition）：将数组分块，每块维护最大值，适合离线批量操作，不适用于高频单点增删。 - 伪代码（Java 风格，可直接实现）： ``` class MaxList { private List data; private Deque maxDeq; // monotonic decreasing private Map counts; public MaxList() { data = new ArrayList<>(); maxDeq = new ArrayDeque<>(); counts = new HashMap<>(); } public void add(int value) { data.add(value); counts.put(value, counts.getOrDefault(value, 0) + 1); // maintain decreasing deque: pop from tail while <= value while (!maxDeq.isEmpty() && maxDeq.peekLast() <= value) { maxDeq.pollLast(); } maxDeq.offerLast(value); } public boolean delete(int value) { int cnt = counts.getOrDefault(value, 0); if (cnt == 0) return false; counts.put(value, cnt - 1); return true; } public int getMax() { // lazy cleanup: remove invalid heads while (!maxDeq.isEmpty() && counts.getOrDefault(maxDeq.peekFirst(), 0) == 0) { maxDeq.pollFirst(); } if (maxDeq.isEmpty()) { throw new NoSuchElementException("MaxList is empty"); } return maxDeq.peekFirst(); } } ``` - 扩展知识：若面试官进一步问“如何支持 getMin 同时存在？”，则升级为「双单调队列」：一个递减（max），一个递增（min），共享同一套 counts 和 data；若要求支持随机访问 get(index)，则主存储必须保留 ArrayList，此时 delete(value) 无法避免扫描（除非额外建值→下标索引，但重复值需 List，退化为 O(n)）；因此，设计始终是权衡：功能需求决定结构选型，十几万数据量下，上述方案在时间、空间、实现复杂度上达到最优平衡。

中企云链挂经

全站热榜

创作者周榜