反悔贪心及例题

摘要

1. 反悔贪心本质也是贪心，只是用堆存了反悔项。

2. 解题时要注意可反悔条件的书写不能遗漏

题目

可以到达的最远建筑（LeetCode 1642）

题目描述

给定建筑物高度数组 heights，以及砖块数 bricks 和梯子数 ladders。从第 0 栋楼出发向右移动： 下坡 / 平路无需消耗资源； 上坡可以用1 架梯子（可跨越任意高度），或消耗等于高度差的砖块。 求最远能到达的建筑物下标。

思路

反悔贪心

一般而言，反悔贪心复杂度为O ( n l o g n ) O(nlogn)O(nlogn)，而DP复杂度为