maximum-sum-queries

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given two 0-indexed integer arrays <code>nums1</code> and <code>nums2</code>, each of length <code>n</code>, and a 1-indexed 2D array <code>queries</code> where <code>queries[i] = [xi, yi]</code>.

For the <code>ith</code> query, find the maximum value of <code>nums1[j] + nums2[j]</code> among all indices <code>j</code> <code>(0 &lt;= j &lt; n)</code>, where <code>nums1[j] &gt;= xi</code> and <code>nums2[j] &gt;= yi</code>, or -1 if there is no <code>j</code> satisfying the constraints.

Return an array <code>answer</code> where <code>answer[i]</code> is the answer to the <code>ith</code> query.

&nbsp;
Example 1:

<pre>
Input: nums1 = [4,3,1,2], nums2 = [2,4,9,5], queries = [[4,1],[1,3],[2,5]]
Output: [6,10,7]
Explanation: 
For the 1st query <code node="[object Object]">xi = 4</code>&nbsp;and&nbsp;<code node="[object Object]">yi = 1</code>, we can select index&nbsp;<code node="[object Object]">j = 0</code>&nbsp;since&nbsp;<code node="[object Object]">nums1[j] &gt;= 4</code>&nbsp;and&nbsp;<code node="[object Object]">nums2[j] &gt;= 1</code>. The sum&nbsp;<code node="[object Object]">nums1[j] + nums2[j]</code>&nbsp;is 6, and we can show that 6 is the maximum we can obtain.

For the 2nd query <code node="[object Object]">xi = 1</code>&nbsp;and&nbsp;<code node="[object Object]">yi = 3</code>, we can select index&nbsp;<code node="[object Object]">j = 2</code>&nbsp;since&nbsp;<code node="[object Object]">nums1[j] &gt;= 1</code>&nbsp;and&nbsp;<code node="[object Object]">nums2[j] &gt;= 3</code>. The sum&nbsp;<code node="[object Object]">nums1[j] + nums2[j]</code>&nbsp;is 10, and we can show that 10 is the maximum we can obtain. 

For the 3rd query <code node="[object Object]">xi = 2</code>&nbsp;and&nbsp;<code node="[object Object]">yi = 5</code>, we can select index&nbsp;<code node="[object Object]">j = 3</code>&nbsp;since&nbsp;<code node="[object Object]">nums1[j] &gt;= 2</code>&nbsp;and&nbsp;<code node="[object Object]">nums2[j] &gt;= 5</code>. The sum&nbsp;<code node="[object Object]">nums1[j] + nums2[j]</code>&nbsp;is 7, and we can show that 7 is the maximum we can obtain.

Therefore, we return&nbsp;<code node="[object Object]">[6,10,7]</code>.
</pre>

Example 2:

<pre>
Input: nums1 = [3,2,5], nums2 = [2,3,4], queries = [[4,4],[3,2],[1,1]]
Output: [9,9,9]
Explanation: For this example, we can use index&nbsp;<code node="[object Object]">j = 2</code>&nbsp;for all the queries since it satisfies the constraints for each query.
</pre>

Example 3:

<pre>
Input: nums1 = [2,1], nums2 = [2,3], queries = [[3,3]]
Output: [-1]
Explanation: There is one query in this example with <code node="[object Object]">xi</code> = 3 and <code node="[object Object]">yi</code> = 3. For every index, j, either nums1[j] &lt; <code node="[object Object]">xi</code> or nums2[j] &lt; <code node="[object Object]">yi</code>. Hence, there is no solution. 
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>nums1.length == nums2.length</code>&nbsp;</li>
	<li><code>n ==&nbsp;nums1.length&nbsp;</code></li>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>1 &lt;= nums1[i], nums2[i] &lt;= 109&nbsp;</code></li>
	<li><code>1 &lt;= queries.length &lt;= 105</code></li>
	<li><code>queries[i].length ==&nbsp;2</code></li>
	<li><code>xi&nbsp;== queries[i][1]</code></li>
	<li><code>yi == queries[i][2]</code></li>
	<li><code>1 &lt;= xi, yi &lt;= 109</code></li>
</ul>

maximumSumQueries

Maximum Sum Queries

Most Beautiful Item for Each Query

most-beautiful-item-for-each-query

每一个查询的最大美丽值

Stack

Binary Indexed Tree

Segment Tree

Array

Binary Search

Sorting

Monotonic Stack

给你两个长度为 <code>n</code> 、下标从 0 开始的整数数组 <code>nums1</code> 和 <code>nums2</code> ，另给你一个下标从 1 开始的二维数组 <code>queries</code> ，其中 <code>queries[i] = [xi, yi]</code> 。

对于第 <code>i</code> 个查询，在所有满足 <code>nums1[j] &gt;= xi</code> 且 <code>nums2[j] &gt;= yi</code> 的下标 <code>j</code> <code>(0 &lt;= j &lt; n)</code> 中，找出 <code>nums1[j] + nums2[j]</code> 的 最大值 ，如果不存在满足条件的 <code>j</code> 则返回 -1 。

返回数组 <code>answer</code> ，其中 <code>answer[i]</code> 是第 <code>i</code> 个查询的答案。

&nbsp;

示例 1：

<pre>输入：nums1 = [4,3,1,2], nums2 = [2,4,9,5], queries = [[4,1],[1,3],[2,5]]
输出：[6,10,7]
解释：
对于第 1 个查询：<code>xi = 4</code>&nbsp;且&nbsp;<code>yi = 1</code> ，可以选择下标&nbsp;<code>j = 0</code>&nbsp;，此时 <code>nums1[j] &gt;= 4</code>&nbsp;且&nbsp;<code>nums2[j] &gt;= 1</code> 。<code>nums1[j] + nums2[j]</code>&nbsp;等于 6 ，可以证明 6 是可以获得的最大值。
对于第 2 个查询：<code>xi = 1</code>&nbsp;且&nbsp;<code>yi = 3</code> ，可以选择下标&nbsp;<code>j = 2</code>&nbsp;，此时 <code>nums1[j] &gt;= 1</code>&nbsp;且&nbsp;<code>nums2[j] &gt;= 3</code> 。<code>nums1[j] + nums2[j]</code>&nbsp;等于 10 ，可以证明 10 是可以获得的最大值。
对于第 3 个查询：<code>xi = 2</code>&nbsp;且&nbsp;<code>yi = 5</code> ，可以选择下标&nbsp;<code>j = 3</code>&nbsp;，此时 <code>nums1[j] &gt;= 2</code>&nbsp;且&nbsp;<code>nums2[j] &gt;= 5</code> 。<code>nums1[j] + nums2[j]</code>&nbsp;等于 7 ，可以证明 7 是可以获得的最大值。
因此，我们返回&nbsp;<code>[6,10,7]</code> 。
</pre>

示例 2：

<pre>输入：nums1 = [3,2,5], nums2 = [2,3,4], queries = [[4,4],[3,2],[1,1]]
输出：[9,9,9]
解释：对于这个示例，我们可以选择下标&nbsp;<code>j = 2</code>&nbsp;，该下标可以满足每个查询的限制。
</pre>

示例 3：

<pre>输入：nums1 = [2,1], nums2 = [2,3], queries = [[3,3]]
输出：[-1]
解释：示例中的查询 <code>xi</code> = 3 且 <code>yi</code> = 3 。对于每个下标 j ，都只满足 nums1[j] &lt; <code>xi</code> 或者 nums2[j] &lt; <code>yi</code> 。因此，不存在答案。 
</pre>

&nbsp;

提示：

<ul>
	<li><code>nums1.length == nums2.length</code>&nbsp;</li>
	<li><code>n ==&nbsp;nums1.length&nbsp;</code></li>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>1 &lt;= nums1[i], nums2[i] &lt;= 109&nbsp;</code></li>
	<li><code>1 &lt;= queries.length &lt;= 105</code></li>
	<li><code>queries[i].length ==&nbsp;2</code></li>
	<li><code>xi&nbsp;== queries[i][1]</code></li>
	<li><code>yi == queries[i][2]</code></li>
	<li><code>1 &lt;= xi, yi &lt;= 109</code></li>
</ul>