想到用单调栈,但是发现对于每个点虽然找到了下一个最大,但是对于题目要求的 [a, b]两点,无法确保找到的下一个最大点一定是>= b的满足
解决方案1
对于每个b记录小于的a,然后从后往前遍历heights,这样再去根据b再去找a. 这样以来单调栈内的元素既是> heights[b]的又是有序的, 所以可以用二分进行快速查找
解决方法2
放弃单调栈,直接使用 heap 基于方案1,维护 heap 即可快速找到第一个最大
想到用单调栈,但是发现对于每个点虽然找到了下一个最大,但是对于题目要求的 [a, b]两点,无法确保找到的下一个最大点一定是>= b的满足
对于每个b记录小于的a,然后从后往前遍历heights,这样再去根据b再去找a. 这样以来单调栈内的元素既是> heights[b]的又是有序的, 所以可以用二分进行快速查找
放弃单调栈,直接使用 heap 基于方案1,维护 heap 即可快速找到第一个最大