1642.Furthest_Building_You_Can_Reach.md

1642. Furthest Building You Can Reach

本來想用 Brute Force 的方式解這題，用 Backtracking 的方式去嘗試每一種可能，但是這樣會超時。

Time Limit Exceeded Solution:

var (
	maxnum_building int
)

func FurthestBuilding(heights []int, bricks int, ladders int) int {
	maxnum_building = 0
	backtracking(heights, bricks, ladders, 0)
	return maxnum_building
}

func backtracking(heights []int, bricks int, ladders int, current int) {
	for i := 0; i < len(heights)-1; i++ {
		height := heights[i] - heights[i+1]
		if height >= 0 {
			current++
		} else {
			if bricks >= -height {
				backtracking(heights[i+1:], bricks+height, ladders, current+1)
			}
			if ladders > 0 {
				backtracking(heights[i+1:], bricks, ladders-1, current+1)
			}
			break
		}
	}
	maxnum_building = intMax(current, maxnum_building)
}

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

---

Greedy Algorithm

這題如果是使用 Greedy Algorithm 的話，只要依照以下步驟就可以解出答案：

1. 優先使用 bricks，直到 bricks 不夠用
   • 並且使用一個資料結構來記錄使用的 bricks，要能夠快速找到最大的 bricks
2. 如果 bricks 不夠用，就使用 ladders
   • 去替換掉過去使用的 bricks 最多次的那一個，這樣的效率最高
3. 重複步驟 1 和 2 直到結束，這樣就可以得到最遠可以到達的樓層

Time Complexity: O(n) * O(logn) = O(nlogn)，除了歷遍的複雜度還要加上 Heap 的複雜度

Max Heap Solution:

• 如果是 golang 的話必須使用 Heap
  • 之前使用一個 binary serach insert 來實現 Priority Queue，也還是會造成 TLE

type IntHeap []int

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

func (h IntHeap) Less(i, j int) bool {
	return h[i] > h[j]
}

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.(int))
}

func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func FurthestBuilding(heights []int, bricks int, ladders int) int {
	maxHeap := &IntHeap{}
	heap.Init(maxHeap)
	for i := 0; i < len(heights)-1; i++ {
		diff := heights[i+1] - heights[i]
		if diff > 0 {
			bricks -= diff
			heap.Push(maxHeap, diff)
			if bricks < 0 {
				if ladders <= 0 {
					return i
				}
				if maxHeap.Len() > 0 {
					bricks += heap.Pop(maxHeap).(int)
				}
				ladders--
			}
		}
	}
	return len(heights) - 1
}