# 2070. Most Beautiful Item for Each Query
###### tags: `Leetcode` `Medium` `Sorting` `TreeMap`
Link: https://leetcode.com/problems/most-beautiful-item-for-each-query/description/
## 思路
### Sorting + Two Pointers
把items和queries都从小到大排列
两个指针分别指items和queries
在移动queries指针的时候items指针也会跟着向右移动
持续记录最大值即可
### TreeMap
先sort items
然后把每个entry的price和当前最大的beauty存进去
对于每一个query只要找floorEntry就可以
## Code
### Sorting + Two Pointers

class Solution {
    public int[] maximumBeauty(int[][] items, int[] queries) {
        int n = queries.length;
        int m = items.length;
        Arrays.sort(items, (a,b)->(a[0]-b[0]));
        int[][] queriesIdx = new int[n][2];
        for(int i=0; i<n; i++){
            queriesIdx[i][0] = queries[i];
            queriesIdx[i][1] = i;
        }
        Arrays.sort(queriesIdx, (a,b)->(a[0]-b[0]));

        int[] ans = new int[n];
        int j = 0;
        int currMax = 0;
        for(int i=0; i<n; i++){
            while(j<m && items[j][0]<=queriesIdx[i][0]){
                currMax = Math.max(currMax, items[j][1]);
                j++;
            }
            ans[queriesIdx[i][1]] = currMax;
        }
        return ans;
    }
}

### TreeMap

class Solution {
    public int[] maximumBeauty(int[][] items, int[] queries) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        Arrays.sort(items, (a,b)->(a[0]-b[0]));
        int currMax = 0;
        map.put(0, 0);
        for(int[] item:items){
            currMax = Math.max(currMax, item[1]);
            map.put(item[0], currMax);
        }
        int[] ans = new int[queries.length];
        for(int i=0; i<queries.length; i++){
            ans[i] = map.floorEntry(queries[i]).getValue();
        }
        return ans;
    }
}