Re: [閒聊] 每日leetcode
算簡單的hard, 滿快就有想法了
不過寫起來有點卡
2163. Minimum Difference in Sums After Removal of Elements
思路 :
這題firstsum要盡量小、secondsum要盡量大
先把前n個elements加起來得到firstsum並且放到MaxHeap裡面
再來將後2*n個元素依照大小排序, 排序後的最大的n個elements總和為secondsum
並且記錄排序前後的index的對照表
接著就是從nums[n]開始
如果nums[i]比MaxHeap中最大的值還小, 就nums[i]替換到firstnum
再來如果nums[i]是在secondsum裡
那就把secondsum-nums[i]並加入剩餘elements中最大的值
這樣就能得到答案了
golang code :
type maxheap []int
func (this maxheap) Len() int { return len(this) }
func (this maxheap) Less(i, j int) bool { return this[i] > this[j] }
func (this maxheap) Swap(i, j int) { this[i], this[j] = this[j], this[i]
}
func (this *maxheap) Push(x interface{}) { *this = append(*this, x.(int)) }
func (this *maxheap) Pop() interface{} {
n := len(*this)
res := (*this)[n-1]
(*this) = (*this)[:n-1]
return res
}
func minimumDifference(nums []int) int64 {
firstSum, secondSum := 0, 0
n := len(nums) / 3
last2nSortByVal := make([][2]int, 2*n)
arr := make([]int, 2*n)
for i := 0; i < 2*n; i++ {
last2nSortByVal[i][0] = i
last2nSortByVal[i][1] = nums[i+n]
}
slices.SortFunc(last2nSortByVal, func(i, j [2]int) int { return i[1] - j[1] }
)
for i := 0; i < 2*n; i++ {
arr[last2nSortByVal[i][0]] = i
}
leftPartHeap := maxheap{}
for i := 0; i < n; i++ {
firstSum += nums[i]
secondSum += last2nSortByVal[2*n-1-i][1]
heap.Push(&leftPartHeap, nums[i])
}
start := n
ans := firstSum - secondSum
rec := make([]bool, 2*n)
for i := 0; i < n; i++ {
numIdx := i + n
if leftPartHeap[0] > nums[numIdx] {
tmp := heap.Pop(&leftPartHeap).(int)
heap.Push(&leftPartHeap, nums[numIdx])
firstSum = firstSum - tmp + nums[numIdx]
}
if arr[i] >= start {
secondSum -= nums[numIdx]
start--
for rec[start] {
start--
}
rec[start] = true
secondSum += last2nSortByVal[start][1]
}
rec[arr[i]] = true
ans = min(ans, firstSum-secondSum)
}
return int64(ans)
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.215.196 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1752853894.A.DF5.html
討論串 (同標題文章)
完整討論串 (本文為第 1474 之 1554 篇)：