请教一道算法题！

1.png

2.png

3.png

基础计算方法不难，就是loop所有bus可以载多少人就好。但是题目要求优化，test case里头有几万列数字，要求15秒内算好。hint说用更好的data structure来求，不知道各位大神能不能帮帮忙。

我的想法是可以优化到max(n,m)logn

首先把队列中的n个耐久度依次放进一个新数组，每次放进去的时候用二分法进行大小比较并且换位，最后在新数组中的位置代表在此之前多少人可以上车。另外储存一个hash，在每一个耐久度放进新数组之后，立即保存/刷新这个耐久度数值和位置的键值对。复杂度nlogn

第二步是对这个键值对按耐久度进行从小到大的排序。复杂度nlogn

然后再根据m个公交车到达的时刻，在第二步获得的数组中进行二分查找。复杂度mlogn

补充内容 (2024-04-08 06:55 +08:00):
抛砖引玉

你可以抽象一下题目。
这道题等同于：
给定一个整型数组 p
给一个下标q[i], 问 p[i] - p[n] 里小于等于q[i]的整数的下标的最大值；比如p[n-1] < q[i] and p[n] > q[i]，那就是n-1

这种题目一般都用单调栈