题目分析

这是第213场周赛的第三题，我觉得这个题目很好，因此拿出来和小伙伴们分享。

贪心

贪心思路非常明显，从0开始到最远的建筑这段距离中，我们的梯子使用在差距最大的楼层一定是最优解。
我们只需要关注后面楼层高于前面楼层的这些位置即可，我们的梯子个数为n，那么我们要把所经过的差距最大的n个楼层使用梯子。因此我们要维护一个大小为n的最小堆，当某个楼层后面的楼层高于它时，如果此时堆的元素小于梯子数，那么可以直接加入，不使用砖块。如果此时堆的元素大于梯子数，此时如果楼层差距delta大于堆顶元素heap[0]，说明堆顶使用砖块会更少一些，因此，已使用砖块个数要加上堆顶元素heap[0]。否则当前楼层使用砖块个数会更少，已使用砖块个数要加上当前delta。

算法的**时间复杂度为$O(nlog(n))$，空间复杂度为$O(n)$**。

import heapq


class Solution(object):
    def furthestBuilding(self, heights, bricks, ladders):
        """
        :type heights: List[int]
        :type bricks: int
        :type ladders: int
        :rtype: int
        """
        heap, cur_brick = [], 0
        for i in range(len(heights) - 1):
            delta = heights[i + 1] - heights[i]
            if delta > 0:
                if len(heap) < ladders:
                    heapq.heappush(heap, delta)
                else:
                    cur_brick += heapq.heappushpop(heap, delta)
                    if cur_brick > bricks:
                        return i
        return len(heights) - 1

二分查找

二分查找也是一个很好的思路，小伙伴们一定要学会，二分查找中点，如果满足条件，则二分查找后半段，如果不满足条件，则二分查找前半段。

判断条件时也是采用贪心的思路，在差异最大的楼层之间使用梯子。非常好理解，直接看代码即可。

二分的时间复杂度为log(n)，在每次判断时要对楼层差异进行排序，因此算法的**时间复杂度为$O(nlog(n)log(n))$，空间复杂度为$O(n)$**。

class Solution(object):
    def furthestBuilding(self, heights, bricks, ladders):
        """
        :type heights: List[int]
        :type bricks: int
        :type ladders: int
        :rtype: int
        """
        def judge(mid):
            tmp = sorted(diff[:mid + 1])
            return bricks >= sum(tmp[:max(0, len(tmp) - ladders)])

        diff = [max(0, heights[i + 1] - heights[i]) for i in range(len(heights) - 1)]
        left, right = 0, len(diff) - 1
        while left < right:
            mid = (left + right) // 2
            if judge(mid):
                left = mid + 1
            else:
                right = mid
        return left + 1 if left == len(diff) - 1 and judge(left) else left

刷题总结

二分查找是一个非常好的思路，这类题型往往都可以考虑这个方法，但是二分查找的难点在于如何写判断函数和控制边界条件，希望小伙伴们可以自己实现一遍，巩固记忆。