每日算法刷题计划Day15 5.25:leetcode不定长滑动窗口求子数组个数越短越合法3道题，用时1h

2.3.2 越短越合法

一般要写 ans += right - left + 1。
内层循环结束后，[left,right] 这个子数组是满足题目要求的。由于子数组越短，越能满足题目要求，所以除了 [left,right]，还有 [left+1,right],[left+2,right],…,[right,right] 都是满足要求的。也就是说，当右端点固定在 right 时，左端点在 left,left+1,left+2,…,right 的所有子数组都是满足要求的，这一共有 right−left+1 个。

• 模版套路

• 套路

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k <= 1)
            return 0;
        int n = nums.size();
        long long product = 1;
        int left = 0;
        int res = 0;
        for (int right = 0; right < n; ++right) {
            // 1.right入窗口，更新统计量
            product *= (long long)nums[right];
            // 2.越短越合法，所以while循环条件为不满足窗口条件
            while (product >= k) {
                product /= (long long)nums[left];
                ++left;
            }
            // 3.此时[left,right]满足窗口条件，固定right，左端点共有[left,right]共right-left+1个子数组
            res += right - left + 1;
        }
        return res;
    }
};

• 题目描述

1.给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k(窗口条件) 的连续子数组的数目。
2.如果一个 二进制字符串 满足以下任一条件(不是所有条件)，则认为该字符串满足 k 约束：

• 字符串中 0 的数量最多为 k。
• 字符串中 1 的数量最多为 k。
  返回一个整数，表示 s 的所有满足 k 约束 (窗口条件)的子字符串的数量。
  3.给你一个下标从 0 开始的整数数组 nums 。nums 的一个子数组如果满足以下条件，那么它是 不间断 的：
• i，i + 1 ，…，j  表示子数组中的下标。对于所有满足 i <= i1, i2 <= j 的下标对，都有 0 <= |nums[i1] - nums[i2]| <= 2(窗口条件) 。
  请你返回 不间断 子数组的总数目。(难点在于如何维护窗口的最小值和最大值，两种思路:按键排序的map或者记录最小下标和最大下标的单调队列(双端队列deque实现))

• 学习经验

1.与越长越合法不同点:
(1)越长越合法right元素进入窗口导致窗口更合法，while条件是窗口成立条件，最终退出while循环让[left,right]不符合窗口条件，固定right，[0,left-1]共left个左端点满足条件
(2)越短越合法right进入窗口导致窗口不合法，while条件是窗口不成立条件，最终退出while循环让[left,right]符合窗口条件，固定right,[left,right]共right-left+1个左端点满足条件

• 1. 713.乘积小于K的子数组(中等，学习)

713. 乘积小于 K 的子数组 - 力扣（LeetCode）

思路

1.给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
2.题目条件nums[i]>=1,所以k<=1答案为0，得先判断

代码

c++:

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
	    // 特殊条件先判断
        if (k <= 1)
            return 0;
        int n = nums.size();
        long long product = 1;
        int left = 0;
        int res = 0;
        for (int right = 0; right < n; ++right) {
            // 1.right入窗口，更新统计量
            product *= (long long)nums[right];
            // 2.越短越合法，所以while循环条件为不满足窗口条件
            while (product >= k) {
                product /= (long long)nums[left];
                ++left;
            }
            // 3.此时[left,right]满足窗口条件，固定right，左端点共有[left,right]共right-left+1个子数组
            res += right - left + 1;
        }
        return res;
    }
};

• 2. 3258.统计满足K约束的子字符串数量I(简单)

3258. 统计满足 K 约束的子字符串数量 I - 力扣（LeetCode）

思路

1.如果一个 二进制字符串 满足以下任一条件，则认为该字符串满足 k 约束：

• 字符串中 0 的数量最多为 k。
• 字符串中 1 的数量最多为 k。
  返回一个整数，表示 s 的所有满足 k 约束 的子字符串的数量。
  2.注意题目要求“满足以下任一条件”，所以while循环里面条件是and,且不好用一个unorderd_map来作为判断条件，其适合所有字符最多为K的情况

代码

c++:

class Solution {
public:
    int countKConstraintSubstrings(string s, int k) {
        int n = s.size();
        int res = 0;
        int cnt0 = 0, cnt1 = 0;
        int left = 0;
        for (int right = 0; right < n; ++right) {
            if (s[right] == '0')
                ++cnt0;
            else
                ++cnt1;
            while (cnt0 > k && cnt1 > k) {
                if (s[left] == '0')
                    --cnt0;
                else
                    --cnt1;
                ++left;
            }
            res += right - left + 1;
        }
        return res;
    }
};

• 3. 2762.不间断子数组(中等，学习)

2762. 不间断子数组 - 力扣（LeetCode）

思想

1.给你一个下标从 0 开始的整数数组 nums 。nums 的一个子数组如果满足以下条件，那么它是 不间断 的：

• i，i + 1 ，…，j  表示子数组中的下标。对于所有满足 i <= i1, i2 <= j 的下标对，都有 0 <= |nums[i1] - nums[i2]| <= 2 。
  请你返回 不间断 子数组的总数目。
  2.不难想到要得到窗口的最大值和最小值，但是只用两个变量的话移出left元素会很麻烦，自己暂时没想到什么好方法，学习一下别人的思路。
  3.思路一：哈希表(简单)
  map是按键排序的，所以可以很方便的得到最小值和最大值，同时记录次数，次数为0的移除即可，学习**cnt.rbegin()->first反向迭代器获取最后一个元素的写法**，不能用cnt.end()->first,因为end()取不到
  4.思路二:两个单调队列(双端队列deque实现)(进阶)
  用两个单调队列分别维护最小值和最大值的下标,最小值单调队列逻辑:
  (1)取单调队列的队首front()元素，所以最小值单调队列是单调递增的，所以新来的right元素如果小于等于单调队列的队尾back()元素，要逐步移出back()元素(前提队列不为空)，保证队列的单调性(取队首，移队尾)
  最大值单调队列同理
  (2)难点在于left元素移出怎么操作单调队列，重点在于单调队列维护的是下标,所以先让left++,如果最小值和最大值下标小于left,那么单调队列要移出队首元素,表示当前窗口没有这个最小值或最大值

代码

c++:
1.思路一：哈希表

class Solution {
public:
    long long continuousSubarrays(vector<int>& nums) {
        int n = nums.size();
        long long res = 0;
        map<int, int> cnt;
        int left = 0;
        for (int right = 0; right < n; ++right) {
            ++cnt[nums[right]];
            while (cnt.rbegin()->first - cnt.begin()->first > 2) {
                --cnt[nums[left]];
                if (cnt[nums[left]] == 0)
                    cnt.erase(nums[left]);
                ++left;
            }
            res += right - left + 1;
        }
        return res;
    }
};

2.思路二:两个单调队列

class Solution {
public:
    long long continuousSubarrays(vector<int>& nums) {
        int n = nums.size();
        long long res = 0;
        deque<int> minq, maxq;
        int left = 0;
        for (int right = 0; right < n; ++right) {
            // 最小下标单调队列单调递增，right元素小于back要在队列不为空的条件下移出back元素
            while (!minq.empty() && nums[right] <= nums[minq.back()])
                minq.pop_back();
            // 最大下标单调队列单调递减，right元素大于back要在队列不为空的条件下移出back元素
            while (!maxq.empty() && nums[right] >= nums[maxq.back()])
                maxq.pop_back();
            minq.push_back(right);
            maxq.push_back(right);
            while (nums[maxq.front()] - nums[minq.front()] > 2) {
                ++left;
                if (minq.front() < left)
                    minq.pop_front();
                if (maxq.front() < left)
                    maxq.pop_front();
            }
            res += right - left + 1;
        }
        return res;
    }
};