支持首元素删除的累积最大值（cummax）算法实现问询

存在这样的数据结构，可以让removeFirst操作达到O(1)的均摊时间复杂度，核心思路是预分段存储累积最大值的"恒定区间"，并为每个区间预先准备好删除首元素后的子分段结构。

核心思路 #

累积最大值（cummax）列表的核心特点是：一旦出现更大的值，后续的累积最大值会保持该值直到遇到新的更大值。基于这一点，我们可以把原数组的累积最大值拆分为若干恒定区间——每个区间内的累积最大值为同一个常量，对应原数组的一段连续索引。

以示例数组[10, 7, 8, 0, 3, 11]为例，其累积最大值的恒定区间为：

• [0-4]：值为10（原数组前5个元素的累积最大值均为10）
• [5-5]：值为11（最后一个元素的累积最大值为11）

我们用链表存储这些区间，每个区间节点包含以下信息：

• start/end：对应原数组的索引范围
• max_val：该区间的累积最大值
• sub_segments：预先计算好的、删除该区间首元素后的子区间链表（即原区间从start+1到end的累积最大值恒定区间）

预处理构建步骤 #

1. 生成初始恒定区间：遍历原数组，记录当前最大值，每当最大值变化时，结束当前区间并开启新的区间。这一步时间复杂度为O(n)。
2. 预先生成子区间：对每个区间，递归或迭代生成其sub_segments：
   • 若区间为单元素区间（start == end），sub_segments为空。
   • 若为多元素区间，计算该区间从start+1到end的累积最大值恒定区间，作为sub_segments。由于每个元素仅被处理一次，这一步的总时间复杂度仍为O(n)。

removeFirst操作实现 #

当需要删除原数组的首元素时，仅需操作链表的头部节点：

1. 取出链表的第一个区间节点：
   • 如果该区间是单元素区间，直接从链表中删除此节点。
   • 如果是多元素区间，将此节点替换为其预存的sub_segments链表。
2. 整个操作仅涉及链表的节点替换或删除，时间复杂度为O(1)。

示例验证 #

• 初始区间链表：[0-4, 10] → [5-5, 11]
• 第一次removeFirst：将[0-4, 10]替换为其sub_segments（[1-1, 7] → [2-4, 8]），链表变为[1-1, 7] → [2-4, 8] → [5-5, 11]，对应累积最大值列表[7, 8, 8, 8, 11]。
• 第二次removeFirst：删除单元素区间[1-1, 7]，链表变为[2-4, 8] → [5-5, 11]，对应累积最大值列表[8, 8, 8, 11]。

复杂度分析 #

• 构建时间：O(n)，遍历数组生成初始区间，预处理子区间的总操作数与原数组元素数成正比。
• removeFirst操作：O(1)均摊时间，每次仅操作链表头部节点，无需遍历整个数组。
• 空间复杂度：O(n)，最坏情况下（原数组严格递增），每个元素对应一个区间，子区间的总数量也为O(n)。

内容的提问来源于stack exchange，提问作者Bakhanov A.