摘要
1. 反悔贪心本质也是贪心,只是用堆存了反悔项。
2. 解题时要注意可反悔条件的书写不能遗漏
题目
可以到达的最远建筑(LeetCode 1642)
题目描述
给定建筑物高度数组 heights,以及砖块数 bricks 和梯子数 ladders。从第 0 栋楼出发向右移动: 下坡 / 平路无需消耗资源; 上坡可以用1 架梯子(可跨越任意高度),或消耗等于高度差的砖块。 求最远能到达的建筑物下标。
思路
反悔贪心
一般而言,反悔贪心复杂度为O ( n l o g n ) O(nlogn)O(nlogn),而DP复杂度为