发表于 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;
      }
  };

• LC 题目链接