主題
題目連結：
題目意譯：
你被給定一個二維整數陣列 items，其中 items[i] = [pricei, beautyi] 依序代表著一件物品的價格以及美麗度。
你同時也被給定一個索引值從 0 開始之整數陣列 queries。對於每筆詢問 queries[j]，你想要判斷價格小於或等於 queries[j] 的物品中最大的美麗度。如果這樣子的物品並不存在，則此筆詢問的答案為 0。
回傳一與 queries 相同長度的陣列 answer，其中 answer[j] 為第 j 筆詢問的答案。
限制：
1 ≦ items.length, queries.length ≦ 10 ^ 5
items[i].length == 2
1 ≦ pricei, beautyi, queries[j] ≦ 10 ^ 9
範例測資：
範例 1：
輸入： items = [[1,2],[3,2],[2,4],[5,6],[3,5]], queries = [1,2,3,4,5,6]
輸出： [2,4,5,5,6,6]
解釋：
- 對於 queries[0] = 1，[1,2] 為唯一一個物品有著價格 ≦ 1。因此對於此次詢問之答案為 2。
- 對於 queries[1] = 2，可考慮的物品為 [1,2] 和 [2,4]。
它們之中最大美麗度為 4。
- 對於 queries[2] = 3 和 queries[3] = 4，可考慮的物品為 [1,2] 、 [3,2] 、 [2,4] 和 [3,5]。
它們之中最大美麗度為 5。
- 對於 queries[2] = 5 和 queries[3] = 6，所有物品皆可考慮。
因此，答案為所有物品中的最大美麗度，即 6。
範例 2：
輸入： items = [[1,2],[1,2],[1,3],[1,4]], queries = [1]
輸出： [4]
解釋：
每件物品的價格都是 1，所以我們選擇最大的美麗度為 4 的物品。
注意到複數的物品可以有著相同的價格或美麗度。
範例 3：
輸入： items = [[10,1000]], queries = [5]
輸出： [0]
解釋：
沒有物品價格小於或等於 5，所以沒物品可選。
因此，此次詢問之答案為 0。
解題思維：
我們將所有物品按照價格由小到大排序，而所有的詢問也按照其要求價格由小到大排序（不過因為我們最後需要填 answer 陣列，所以需要記錄其原本的索引值）。
排序後我們便可以看到，現在對於所有的 i > 0，queries[i - 1] 所考慮的物品必不多於 queries[i]。也就是說，根據價格排序之後我們的詢問之價格是非遞減的，所以只可能有更多候選物品可供考慮，不會變少。
也就是說 queries[i] 考慮的物品中的美麗度最大值要不是來自於 queries[i - 1] 的答案，就是來自於新考慮的物品之中。
因此假設 queries[i - 1] 需要考慮 items[0] ～ items[j]（這邊的 items 陣列是排序後的），已知其中最大美麗度為 M；而 queries[i] 需要考慮 items[0] ～ items[k]（其中 j ≦ k），因此 queries[i] 的答案即為
max(M, items[j + 1], items[j + 2], ……, items[k])
可以看到先前考慮過的物品實際上不需重新考慮。
因此最糟糕的情況是掃完所有詢問後所有物品都有被考慮過一次，得時間複雜度為 O(items.length + queries.length)。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
