240309 LeetCode刷题总结

239 滑动窗口最大值

LeetCode248. 滑动窗口最大值

解题思路

将窗口固定，移动数组，移入窗口中的数，又新又大的数最好，又老又小最差。依照此思想可以维护一个单调队列，队列中的元素是当前窗口内的元素的子集。在这个队列中，只保存有可能成为最大值的数，不可能成为最大值的数都要被剔除。维护队列的递减顺序，即可在队首获得当前区间的最大值。为了满足以上要求，要设计出入队规则。

入队规则：入队的元素必然是最新的元素。如果该元素比队列中一部分元素更大，那么这部分元素必然不可能成为最大值(没人年轻还没人厉害直接被卷死了)，我们将这部分元素移除出队，将新元素入队。由于我们规定队列递减，所以可以从对尾开始比较，逐个移除比当前元素小的元素，然后从对位加入队列。按照此规则，队列仍然是递减的，没有破坏递减性。如果该元素不比任何元素大，直接放在队尾，虽然人家不大，但是人家年轻有前途，后续的窗口中它仍然有可能成为最大值，依此也不破坏递减性。

出队规则：出队规则更加关键，按照我们之前的定义，元素离开窗口就必须从队列中移除，很自然的想到离开窗口的元素我们可以从队列中寻找它然后移除，但是这样复杂度很高，并且实际上也没有必要。实际上，只有当离开窗口的元素恰好是当前窗口的最大值，也就是队列首元素时我们才需要执行移除操作，理由如下：假设这个离开的元素不是队列中的最大值，那么一定存在一个比他更大的元素位于队列中；另外，我们可以肯定要离开的元素是队列中最老的元素。至此可以推出，队列中必然存在一个元素，比当前要离开的元素更大，且更新，这与我们最开始的确定的条件是冲突的，产生了矛盾，所以假设不成立。或者换句话说，这个元素原本可能存在在队列中，但是它一定会在某一个在它之后并且还比他大的元素入队时，被入队规则剔除掉。于是我们完成了证明，只有离开窗口的元素恰好是当前窗口的最大值也就是队首元素时，我们需要执行出队操作，移除首元素。

在每次入队和出队后，将队列首的元素值记录下来，也就得到了答案。

代码实现

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        deque<int> que;
        // 初始化
        for (int i = 0;i < k;i++)
        {
            push(que, nums[i]);
        }
        ans.push_back(que.front());
        // 一出一进
        for (int i =k, j = nums.size();i < j;i++)
        {
            push(que, nums[i]);
            pop(que, nums[i - k]);
            ans.push_back(que.front());
        }
        return ans;
    }

    void push(deque<int> &que, int x)
    {
        while(!que.empty() && x > que.back()) // 实际上是这里的比较与剔除形成并维护了单调
        {
            que.pop_back();
        }
        que.push_back(x);
    }

    void pop(deque<int> &que,int x)
    {
        if (!que.empty() && que.front() == x)
        {
            que.pop_front();
        }
    }
};

运行结果

76 最小覆盖字串

LeetCode76. 最小覆盖子串

实现代码

class Solution {
public:
    string minWindow(string s, string t) {
        int tar[53] = {0};
        int count[53];
        int l = 0;
        int r = 0;
        int n = s.size();
        int m = t.size();
        int len = 0x3f3f3f;
        string ans;
        for (int i = 0;i < m;i++)
        {
            tar[getI(t[i])]++;
        }


        while(r < n)
        {
            // 跳过不关心的字母
            if (tar[getI(s[r])] == 0)
            {
                r++;
                continue;
            }
            // 关心的字母计数加一
            count[ getI(s[r]) ]++;

            // 计数改变后检查是否满足条件，不满足继续向右扩展窗口
            if (test(tar,count))
            {
                // 满足条件即代表当前窗口(闭区间)中有一个局部解，进入缩小窗口循环
                while (r - l + 1 >= m)
                {
                    // 跳过不关心的字母
                    if (tar[getI(s[l])] == 0)
                    {
                        l++;
                        continue;
                    }
                    // 关心字母计数减一
                    count[ getI(s[l]) ]--;
                    // 计数改变后检查是否满足条件，满足条件证明还未找到局部最优解，继续缩小窗口
                    if (!test(tar,count))
                    {
                        // 不满足条件，代表去掉当前左指针字母后不符合条件，即当前窗口闭区间内是一个局部解
                        // 优于全局最优解时更新
                        if(r - l + 1 < len)
                        {
                            len = r-l+1;
                            ans = s.substr(l,len);
                        }
                        // 移动左指针直到指向下一个关心的字母
                        l++;
                        while (r - l + 1 >= m && tar[getI(s[l])] == 0)
                        {
                            l++;
                        }
                        // 此时窗口已不满足条件，需要向右扩大窗口，跳出缩小窗口循环
                        break;
                    }

                    // 缩小窗口
                    l++;
                }
            }
            
            // 向右扩展
            r++;
        }
        return ans;
    }

    int getI(char x)
    {
        if(x > 'Z')
            return x-'a'+26;
        return x-'A';
    }

    bool test(int* tar, int* count)
    {
        for (int i = 0;i < 52; i++)
        {
            if(count[i] < tar[i]) return false;
        }
        return true;
    }
};

复杂度分析

时间复杂度O(n+m)

运行结果

560 和为 K 的子数组

560. 和为 K 的子数组

解题思路

需要计算子数组的和，可以使用前缀和减少计算次数。但是由于数字中可能出现负数与0，所以前缀和数组并不单调，后续寻找子数组时就不可以使用双指针。注意到题目不需要具体解，只需要解的个数，因此不需要完整存储所有前缀和和坐标，只需将计算过的前缀和进行计数，记录各个前缀和的值的数量。每计算一个前缀和，寻找与当前的前缀和的差为k的对应前缀和的个数，对应前缀和的个数就是以当前指针指向的元素为重点的符合条件的子数组个数。由于我们从头向尾遍历数组，计算前缀和的，并且每个前缀和向前查找匹配的前缀和，因此并不需要前缀和记录的是有序的，于是可以使用unordered_map记录前缀和个数，它的查询操作是O(1)的，可以保证整个算法过程是O(n)的。

实现代码

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        int ans = 0;
        int sum = 0;
        unordered_map<int,int> sumcnt;
        // 0的个数置1很重要，它相当于preSum[-1] = 0，保证了操作的一致性
        sumcnt[0] = 1;
        for (int i = 0; i < n;i++)
        {
            sum += nums[i];
            auto temp = sumcnt.find(sum - k);
            if (temp != sumcnt.end())
                ans += temp->second;
            sumcnt[sum]++;
        }
        return ans;
    }
};

复杂度分析

时间复杂度O(n)

运行结果