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了