leetcode5912 每一个查询的最大美丽值

题目链接：https://leetcode-cn.com/problems/most-beautiful-item-for-each-query/

针对题目给定的 items = {{price_i, beauty_i}}，我们可以先对价格进行排序，使其按照价格从小到大的顺序排列。
在这里，最朴素的做法是，根据每次查询的价格，即 queries[i]，然后遍历 items 中所有价格小于等于 queries[i] 的元素，找最大值，这一过程的时间复杂度为O(n)，加上所有的查询，总的时间复杂度为 O(nq)，这样会导致超时。

我们考虑一种优化方案，首先我们还是对价格从小达到排序，并且我们利用一次遍历，从 items[0][1] 开始，找最大值，并依次传递给后面的元素，
即更新公式：items[i][1] = max(items[i][1], items[i-1][1])，这样保证了当价格小于等于items[i][0]时，有最大的美丽值，即items[i][1]。

在这里，有一种很天真的想法，一直环绕在脑中，既然我们知道了 items[i][0] 对应的 items[i][1] 就是我们要找的答案，那不是可以通过 queries[i] 直接获取吗？
很遗憾的是，虽然 items 是按价格从小到大排序的，但是我们并不清楚具体的某个价格所在的下标，那么我们就无法以O(1) 的代价访问它，如果用遍历 items 的方式去获取，那么时间复杂度还是 O(nq)。上面我们更新了 items[i][1]，在这里，就是构造数组单调性的过程，自然想到了用二分法。并且要找 target的右边界。

如果 items = {{3, 2}, {3, 5}} 这样的情况，必须要搜索右边界才能得到正确的答案

class Solution {
    private int query(int[][] items, int l, int r, int target) {
        while(l < r) {
            int mid = (l + r) / 2;
            if(items[mid][0] == target) {
                l = mid + 1;
            }else if(items[mid][0] < target){
                l = mid + 1;
            }else{
                r = mid;
            }
        }
        if(l == 0) {
            return 0;
        }else{
            return items[l-1][1];
        }
    }
    public int[] maximumBeauty(int[][] items, int[] queries) {
        // 按价格从小到大进行排序
        Arrays.sort(items, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        // 为使用二分搜索，构造单调性
        // 因为现在已经对价格排好序，我们通过一次遍历，记录小于或等于当前价格对应的最大美丽值
        int maxBeauty = items[0][1];
        for(int i = 0; i < items.length; i++) {
            items[i][1] = Math.max(maxBeauty, items[i][1]);
            maxBeauty = items[i][1];
        }
        // 进行查询
        // 在这里讲一下为什么要用二分搜索
        // 上面我们对价格进行了排序，如果给定一个queries[i],搜索价格小于等于它的最大美丽值所需时间复杂度为O(n)
        // 而用二分搜索法，则为O(logn)
        // 整体的时间复杂度从O(n*n) 变为 O(nlogn)
        int[] ans = new int[queries.length];
        for(int i = 0; i < queries.length; i++) {
            ans[i] = query(items, 0, items.length, queries[i]);
        }
        return ans;
    }
}