问题描述
You are given an integer array heights representing the heights of buildings, some bricks, and some ladders.
You start your journey from building 0 and move to the next building by possibly using bricks or ladders.
While moving from building i to building i+1 (0-indexed),
If the current building’s height is greater than or equal to the next building’s height, you do not need a ladder or bricks. If the current building’s height is less than the next building’s height, you can either use one ladder or (h[i+1] - h[i]) bricks. Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.
Example 1:
Input: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
Output: 4 Explanation: Starting at building 0, you can follow these steps:
- Go to building 1 without using ladders nor bricks since 4 >= 2.
- Go to building 2 using 5 bricks. You must use either bricks or ladders because 2 < 7.
- Go to building 3 without using ladders nor bricks since 7 >= 6.
- Go to building 4 using your only ladder. You must use either bricks or ladders because 6 < 9. It is impossible to go beyond building 4 because you do not have any more bricks or ladders.
Example 2:
Input: heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
Output: 7
Example 3:
Input: heights = [14,3,19,3], bricks = 17, ladders = 0
Output: 3
Constraints:
- 1 <= heights.length <= 10^5
- 1 <= heights[i] <= 10^6
- 0 <= bricks <= 10^9
- 0 <= ladders <= heights.length
问题分析
分析题意可知，遇到“低–高”落差时，可以使用砖块或者梯子继续前进；且梯子没有高度限制，这是一个非常重要的隐藏条件；那么我们可以得出：在砖块有限的情况下，落差值大的应该优先使用梯子，梯子使用完后，再使用砖块；这样才能尽可能的走的远
因此，我们可以维护一个最小堆，堆元素的数量就是梯子数量；再维护一个已使用砖块的数量usebricks；然后遍历heights数组，将前ladders个较大的落差值维护在最小堆中，如果有元素从最小堆中被“排挤”出来，说明这个不是前K大的，需要使用砖块，那么usebricks加上这个值即可，最后如果usebricks如果大于砖块总数量，终止循环
综上，代码如下:
示例代码
// 最优解: 将落差最高的前ladders个使用梯子，剩下的使用bricks
// 维护一个最小堆，保存前 ladders 大的差值；
// 其余差值和记为 sum; 遍历直至 sum > bricks, 此时能够到达的最远building即为所求
func furthestBuilding(heights []int, bricks int, ladders int) int {
ans := 0
usebricks := 0
minheap := NewMinheap(ladders)
for i := 1; i < len(heights); i++ {
gap := heights[i] - heights[i-1]
if gap <= 0 {
ans = i
continue
}
usebricks += minheap.Add(gap)
if usebricks > bricks {
break
}
ans = i
}
spew.Dump(minheap)
return ans
}
type minheap struct {
size int
list []int
}
func NewMinheap(size int) *minheap {
return &minheap{
size: size,
}
}
func (m *minheap) Add(val int) int {
if m.size == 0 {
return val
}
// 堆未满，直接append
if len(m.list) < m.size {
m.list = append(m.list, val)
// 自底向上堆化
m.adjustFromBottom()
return 0
}
// 堆已满，判断与root元素的大小关系
if val <= m.list[0] {
return val
}
// 如果比堆顶元素要大，则覆盖堆顶元素，自顶向下堆化
res := m.list[0]
m.list[0] = val
m.adjustFromRoot()
return res
}
// 自顶向下堆化
func (m *minheap) adjustFromRoot() {
for i := 0; i < len(m.list); i++ {
swapidx := i
left, right := 2*i+1, 2*i+2
// 如果不存在子树，终止循环
if swapidx >= len(m.list) {
break
}
// 如果左子树存在且左节点值小于当前值，则左节点为待交换的点
if left < len(m.list) && m.list[i] > m.list[left] {
swapidx = left
}
// 如果右子树也存在，且右节点的值小于当前值 或者 左节点，则待交换点为右节点
if right < len(m.list) && m.list[swapidx] > m.list[right] {
swapidx = right
}
// 如果待交换的点为自身，说明已经堆化完成
if swapidx == i {
break
}
m.list[i], m.list[swapidx] = m.list[swapidx], m.list[i]
// 下一轮迭代开始时，i会自增，因此这里注意减1
i = swapidx - 1
}
}
// 自底向上堆化
func (m *minheap) adjustFromBottom() {
for i := len(m.list) - 1; i >= 1; i-- {
if m.list[i] >= m.list[(i-1)/2] {
break
}
m.list[i], m.list[(i-1)/2] = m.list[(i-1)/2], m.list[i]
i = (i-1)/2 + 1
}
}
v1.5.2