题目来源

https://leetcode.cn/leetbook/read/meituan/oh4ykh/

问题描述

小美是美团仓库的管理员，她会根据单据的要求按顺序取出仓库中的货物，每取出一件货物后会把剩余货物重新堆放，使得自己方便查找。已知货物入库的时候是按顺序堆放在一起的。如果小美取出其中一件货物，则会把货物所在的一堆物品以取出的货物为界分成两堆，这样可以保证货物局部的顺序不变。

已知货物最初是按 1~n 的顺序堆放的，每件货物的重量为 w[i] ,小美会根据单据依次不放回的取出货物。请问根据上述操作，小美每取出一件货物之后，重量和最大的一堆货物重量是多少？

反向添加+并查集

图解

按照与取货相反的顺序，不断添加货物。

然后使用并查集，将添加的第 x 个货物与其左 x−1 右 x+1 两边的货物堆进行合并，合并的前提是：

1. x−1 和 x+1 的下标合法

2. x−1 和 x+1 已经存在（即已经添加过）

然后在添加和合并的过程中维护最大值即可。

首先，这里判断新插入的x是否可以跟左右的合并成一堆，首先判断下标是否合法，然后判断左右的是否出现过（sum[y]），如果出现过，那么假设将数值2指向数值3，那么数值3的和（sum[y])为3+2=5。

mx = max(mx, sum[x])的作用就是判断，如果新出现的是孤立的，即不能合并，那么就输出最大值。这里新出现的是5，那么无法合并。

这里sum[0] = 5, sum[1] = 2, 然后并查集查找合并。

答案是上一轮记下的。