算法题解-滑动窗口

本文是对算法中的滑动窗口板块刷题时的一些思路和解题方法总结.

简单题

1984. 学生分数的最小差值(窗口不变)

这是2022年2月11日的每日一题, 一开始没有理解题目的意思, 这里我分析一下:

给定一个数组nums, 从中任取k个元素, 求k个元素的『最大值与最小值的差』.

一开始容易理解为任意两个值之间的差的最小值, 这是错误的, 举个例子.

nums = [3,2,3,2,5,3,4];
k = 3;

答案应该是0, 因为可以取出三个3, 差值为0.

其实这道题目很简单, 我们需要取出的k个数差值最小, 那么这k个数一定是最靠近的, 那么怎么实现靠近这个条件呢? 就可以先对数组进行排序, 然后看k个一组的首尾差值即可.

这里倒是用不上双指针, 毕竟窗口大小不变, 可以使用k直接来约束.

代码如下:

class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        if(k == 1) {
            return 0;
        }
        sort(nums.begin(), nums.end());
        // 初始为最大值
        int res = 100000;
        for(int left = 0; left+k-1 < nums.size(); left++) {
            res = min(res, nums[left+k-1]-nums[left]);
        }
        return res;
    }
};

中等题

CV题

个人收获