題目來源

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

問題描述

小美是美團倉庫的管理員，她會根據(jù)單據(jù)的要求按順序取出倉庫中的貨物，每取出一件貨物后會把剩余貨物重新堆放，使得自己方便查找。已知貨物入庫的時候是按順序堆放在一起的。如果小美取出其中一件貨物，則會把貨物所在的一堆物品以取出的貨物為界分成兩堆，這樣可以保證貨物局部的順序不變。

已知貨物最初是按 1~n 的順序堆放的，每件貨物的重量為 w[i] ,小美會根據(jù)單據(jù)依次不放回的取出貨物。請問根據(jù)上述操作，小美每取出一件貨物之后，重量和最大的一堆貨物重量是多少？

反向添加+并查集

圖解

按照與取貨相反的順序，不斷添加貨物。

然后使用并查集，將添加的第?x?個貨物與其左?x?1?右?x+1?兩邊的貨物堆進行合并，合并的前提是：

1. x?1?和?x+1?的下標合法

2. x?1?和?x+1?已經(jīng)存在（即已經(jīng)添加過）

然后在添加和合并的過程中維護最大值即可。

首先，這里判斷新插入的x是否可以跟左右的合并成一堆，首先判斷下標是否合法，然后判斷左右的是否出現(xiàn)過（sum[y]），如果出現(xiàn)過，那么假設(shè)將數(shù)值2指向數(shù)值3，那么數(shù)值3的和（sum[y])為3+2=5。

mx = max(mx, sum[x])的作用就是判斷，如果新出現(xiàn)的是孤立的，即不能合并，那么就輸出最大值。這里新出現(xiàn)的是5，那么無法合并。

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

答案是上一輪記下的。