An array is considered special if every pair of its adjacent elements contains two numbers with different parity.
You are given an array of integer nums and a 2D integer matrix queries, where for queries[i] = [fromi, toi] your task is to check that subarray nums[fromi..toi] is special or not.
Return an array of booleans answer such that answer[i] is true if nums[fromi..toi] is special.
Example 1:
Input: nums = [3,4,1,2,6], queries = [[0,4]]
Output: [false]
Explanation:
The subarray is [3,4,1,2,6]. 2 and 6 are both even.
Example 2:
Input: nums = [4,3,1,6], queries = [[0,2],[2,3]]
Output: [false,true]
Explanation:
[4,3,1]. 3 and 1 are both odd. So the answer to this query is false.[1,6]. There is only one pair: (1,6) and it contains numbers with different parity. So the answer to this query is true.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1051 <= queries.length <= 105queries[i].length == 20 <= queries[i][0] <= queries[i][1] <= nums.length - 1class Solution {
public long maximumTripletValue(int[] nums) {
int n = nums.length, maxm = 0, diffMax = 0;
long ans = 0;
for (int k = 0; k < n; k++) {
ans = Math.max(ans, (long) diffMax * nums[k]);
diffMax = Math.max(diffMax, maxm - nums[k]);
maxm = Math.max(maxm, nums[k]);
}
return ans;
}
}class Solution {
public boolean[] isArraySpecial(int[] nums, int[][] queries) {
int[] streak = new int[nums.length];
boolean[] special = new boolean[queries.length];
for (int i = 1; i < nums.length; i++)
if (nums[i] % 2 != nums[i - 1] % 2)
streak[i] = streak[i - 1] + 1;
for (int i = 0; i < queries.length; i++) {
int[] q = queries[i];
if (streak[q[1]] - streak[q[0]] == q[1] - q[0])
special[i] = true;
}
return special;
}
}