3n 块披萨

这道题的思路是使用贪心算法加上双向链表和最小堆。首先，为了方便处理环形数组，我们在数组两端各添加一个0，并建立双向链表来表示这个环。我们的目标是在每一轮中选择一个披萨片，使得当前披萨片加上相邻两个披萨片的总和最大，然后删除这三个披萨片，并更新相邻披萨片的值。为了快速找到这样的披萨片，我们使用最小堆来维护每个披萨片及其相邻披萨片的总和。每次从堆中取出最小的元素，检查其是否已经被删除（由于堆的延迟删除特性），如果没有被删除，则更新总和并进行相应的删除和更新操作。这个过程重复进行k次，其中k是披萨片总数除以3。

时间复杂度: O(nlogn)

空间复杂度: O(n)

class Solution:
    def maxSizeSlices(self, arr: List[int]) -> int:
        n=len(arr)
        k=n//3
        arr=[0]+arr+[0]
        h=[]
        pre=[0]*(n+2)  # 前驱
        nxt=[0]*(n+2)  # 后继
        vis=[False]*(n+2)  # 是否删除了
        for i in range(1,n+1):
            pre[i]=i-1
            nxt[i]=i+1
            heappush(h,(-arr[i],i))
        pre[1]=n
        nxt[n]=1
        def remove(x):
            nxt[pre[x]]=nxt[x]
            pre[nxt[x]]=pre[x]
            vis[x]=True
        tot=0
        for _ in range(k):
            while h and vis[h[0][1]]:
                heappop(h)
            if len(h)==0:
                break
            val,idx=heappop(h)
            val*=-1
            tot+=val
            arr[idx]=arr[pre[idx]]+arr[nxt[idx]]-val
            heappush(h,(-arr[idx],idx))
            remove(pre[idx])
            remove(nxt[idx])
            
        return tot