leetcode1388_go_3n块披萨

题目

给你一个披萨，它由 3n 块不同大小的部分组成，现在你和你的朋友们需要按照如下规则来分披萨：

你挑选任意一块披萨。

Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。

Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。

重复上述过程直到没有披萨剩下。

每一块披萨的大小按顺时针方向由循环数组 slices 表示。

请你返回你可以获得的披萨大小总和的最大值。

示例 1：输入：slices = [1,2,3,4,5,6] 输出：10

解释：选择大小为 4 的披萨，Alice 和 Bob 分别挑选大小为 3 和 5 的披萨。

然后你选择大小为 6 的披萨，Alice 和 Bob 分别挑选大小为 2 和 1 的披萨。你获得的披萨总大小为 4 + 6 = 10 。

示例 2：输入：slices = [8,9,8,6,1,1] 输出：16

解释：两轮都选大小为 8 的披萨。如果你选择大小为 9 的披萨，你的朋友们就会选择大小为 8 的披萨，这种情况下你的总和不是最大的。

示例 3：输入：slices = [4,1,2,5,8,3,1,9,7] 输出：21

示例 4：输入：slices = [3,1,2] 输出：3

提示：1 <= slices.length <= 500

slices.length % 3 == 0

1 <= slices[i] <= 1000

解题思路分析

1、动态规划；时间复杂度O(n^2)，空间复杂度O(n)

func maxSizeSlices(slices []int) int {
   a := calculate(slices[1:])             // 去除第一个数
   b := calculate(slices[:len(slices)-1]) // 去除最后一个数
   return max(a, b)
}

func calculate(slices []int) int {
   n := len(slices)
   target := (n + 1) / 3
   dp := make([][]int, n+1) // dp[i][j] => 在前i个数，选择j个不相邻的数的最大和
   for i := 0; i <= n; i++ {
      dp[i] = make([]int, target+1)
   }
   for i := 1; i <= n; i++ {
      for j := 1; j <= target; j++ {
         var a, b int
         if 2 <= i {
            a = dp[i-2][j-1]
         }
         a = a + slices[i-1] // 选择第i-1个数
         b = dp[i-1][j]      // 不选第i-1个数
         dp[i][j] = max(a, b)
      }
   }
   return dp[n][target]
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}

2、堆；时间复杂度O(nlog(n))，空间复杂度O(n)

var m map[int][2]int

func maxSizeSlices(slices []int) int {
   n := len(slices)
   target := n / 3
   intHeap := make(IntHeap, 0)
   heap.Init(&intHeap)
   m = make(map[int][2]int)
   for i := 0; i < n; i++ {
      left := (i - 1 + n) % n
      right := (i + 1) % n
      m[i] = [2]int{left, right} // 第i个数左右两边位置
      heap.Push(&intHeap, [2]int{slices[i], i})
   }
   res := 0
   visited := make([]bool, n)
   for i := 0; i < target; {
      top := heap.Pop(&intHeap).([2]int)
      value, index := top[0], top[1]
      if visited[index] == true { // 当前序号不可用
         continue
      }
      i++
      left, right := m[index][0], m[index][1]
      visited[left], visited[right] = true, true
      res = res + value
      slices[index] = slices[left] + slices[right] - value // 更新当前序号的值为反悔值
      heap.Push(&intHeap, [2]int{slices[index], index})    // 重新赋值放回堆
      reconnect(left)                                      // 更改左边数的指针
      reconnect(right)                                     // 更改右边数的指针
   }
   return res
}

func reconnect(index int) {
   left, right := m[index][0], m[index][1]
   m[right] = [2]int{left, m[right][1]}
   m[left] = [2]int{m[left][0], right}
}

type IntHeap [][2]int

func (h IntHeap) Len() int {
   return len(h)
}

// 小根堆<,大根堆变换方向>
func (h IntHeap) Less(i, j int) bool {
   return h[i][0] > h[j][0]
}

func (h IntHeap) Swap(i, j int) {
   h[i], h[j] = h[j], h[i]
}

func (h *IntHeap) Push(x interface{}) {
   *h = append(*h, x.([2]int))
}

func (h *IntHeap) Pop() interface{} {
   value := (*h)[len(*h)-1]
   *h = (*h)[:len(*h)-1]
   return value
}