1642. Furthest Building You Can Reach
给你一个array heights 和两个int bricks、ladders
heights表示建筑物的高度
当你从一个矮的建筑物到一个高的建筑物有两种方法
1.用一个ladder
2.用heights[i+1]-heights[i]个bricks
请问你最远可以到第几个建筑物
思路
ladder要用在最大的高度差
假设有n个ladder
用一个heap去纪录前n个最大的高度差
当heap的里有n+1个值，就把最小的pop出来
然后将bricks减去pop出来的那个值
当bricks小于0的时候代表没办法再继续往下一个建筑物前进
type h struct{ sort.IntSlice }
func (this *h) Push(x interface{}) { this.IntSlice = append((this.IntSlice), x
.(int)) }
func (this *h) Pop() interface{} {
n := len(this.IntSlice)
x := this.IntSlice[n-1]
this.IntSlice = this.IntSlice[:n-1]
return x
}
func furthestBuilding(heights []int, bricks int, ladders int) int {
h := h{}
n := len(heights)
idx := 1
for idx < n {
diff := heights[idx] - heights[idx-1]
if diff > 0 {
heap.Push(&h, diff)
if h.Len() > ladders {
bricks -= heap.Pop(&h).(int)
if bricks < 0 {
return idx - 1
}
}
}
idx++
}
return n - 1
}
你版人都跟vt私下约泡
只剩我还在解每日
我想找个大楼楼顶iwin了