JZX轻语：简
LeetCode 3152 - 特殊数组 II
发表于2024年08月14日
一开始的想法是：先从左到右遍历数组，将不满足nums[i] % 2 != nums[i + 1] % 2的下标存入invalid_inx_vec；然后对于每个查询，使用二分法找到from和to之间的第一个不满足条件的下标，如果存在则返回false，否则返回true。这种做法的时间复杂度为O(nlogn)。
后面参考了官方题解，发现可以使用动态规划的方法，时间复杂度为O(n)：使用dp[i]表示以nums[i]结尾的满足条件的最长子数组长度，那么对于每个查询，只需要判断to - from + 1 <= dp[to]即可。
一开始的做法：
class Solution {
public:
vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& queries) {
// invalid_inx_vec存储不满足条件的下标
vector<int> invalid_inx_vec;
for (int i = 0; i < nums.size() - 1; ++i)
if (nums[i] % 2 == nums[i + 1] % 2) invalid_inx_vec.push_back(i);
vector<bool> ans(queries.size(), true);
for (int i = 0; i < queries.size(); ++i) {
auto from = queries[i][0], to = queries[i][1];
// 二分法找到from和to之间的第一个不满足条件的下标
int left = 0, right = invalid_inx_vec.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (invalid_inx_vec[mid] >= from) right = mid - 1;
else left = mid + 1;
}
// 如果存在不满足条件的下标，则返回false
if (left < invalid_inx_vec.size() && invalid_inx_vec[left] < to) ans[i] = false;
}
return ans;
}
};参照官解改进的做法：
class Solution {
public:
vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& queries) {
// dp[i]表示以nums[i]结尾的满足条件的最长子数组长度
vector<int> dp(nums.size(), 1);
for (int i = 1; i < nums.size(); ++i)
if (nums[i] % 2 != nums[i - 1] % 2) dp[i] = dp[i - 1] + 1;
vector<bool> ans(queries.size(), true);
for (int i = 0; i < queries.size(); ++i) {
auto from = queries[i][0], to = queries[i][1];
auto len = to - from + 1;
ans[i] = dp[to] >= len;
}
return ans;
}
};