Day20260309#

滑动窗口最大值#

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

题解#

一眼单调队列的题目

1
class Solution {
2
public:
3
    deque<int> dq;
4
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
5
        for(int i=0;i<k;i++){
6
            while( !dq.empty() && nums[i] > nums[dq.back()]){
7
                dq.pop_back();
8
            }
9
            dq.push_back(i);
10
        }
11
        vector<int> ans;
12
        ans.push_back(nums[dq.front()]);
13

14
        for(int i=1;i<nums.size()-k+1;i++){
15
            while( !dq.empty() && nums[i+k-1] > nums[dq.back()]){
16
                dq.pop_back();
17
            }
18
            dq.push_back(i+k-1);
19
            while(dq.front() < i){
20
                dq.pop_front();
21
            }
22

23
            ans.push_back(nums[dq.front()]);
24
        }
25

26
        return  ans;
27

28

29
    }
30
};

最小覆盖字串#

给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的最短窗口子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""

题解#

对于这样无顺序的字符集，首先考虑的就是hash 先对t字符串用一个hash表记录其中的字符个数，再使用一个hash表动态的记录s串滑动窗口内的字符数量

然后使用滑动窗口，用两个指针，先不断增大r指针，直到s串的哈希表覆盖t串哈希表，然后再增大l指针缩小滑动窗口，直到最小。l再增大1。最后重复上述操作，直到r到s末尾。

1
class Solution {
2
public:
3
    typedef unordered_map<char,int> Hashmap;
4
    bool check(Hashmap& sMap,Hashmap& tMap){
5
        for(auto i:tMap){
6
            if(sMap.find(i.first) == sMap.end()){
7
                return false;
8
            }else if(sMap[i.first] < i.second){
9
                return false;
10
            }
11
        }
12
        return true;
13
    }
14

15
    string minWindow(string s, string t) {
16
        if(t.size() > s.size() ) return "";
17
        Hashmap tMap;
18
        Hashmap sMap;
19

20
        for(int i=0;i<t.size();i++){
21
            tMap[t[i]] ++;
22
        }
23

24
        int l=0,r=0;
25

26
        vector<string> ans;
27

28
        while( r < s.size() && l < s.size()){
29
            while(!check(sMap,tMap) && r<s.size()){
30
                sMap[s[r++]] ++;
31
            }
32

33
            if(r >= s.size()&&!check(sMap,tMap)) break;
34

35
            while(check(sMap,tMap) && l < r){
36
                sMap[s[l++]] --;
37
            }
38
            ans.push_back(s.substr(l-1,r-l+1));
39
        }
40

41

42
        if(ans.size() == 0) return "";
43
        sort(ans.begin(),ans.end(),[](string& s1, string& s2){
44
            return s1.size() < s2.size();
45
        });
46

47
        // for(auto i:ans) {
48
        //     cout<<i<<'\n';
49
        // }
50

51
        return ans[0];
52

53
    }
54
};

合并区间#

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

题解#

对starti 排序，然后遍历，不是很难

1
class Solution {
2
public:
3
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
4
        sort(intervals.begin(),intervals.end(),
5
        [](vector<int>& v1,vector<int>& v2){
6
            return v1[0] < v2[0];
7
        });
8

9
        vector<vector<int> > res;
10

11
        int l = intervals[0][0],r = intervals[0][1];
12
        for(auto item:intervals){
13
            if(item[0] <= r){
14
                r = max(item[1],r);
15
            }else{
16
                res.push_back({l,r});
17
                l = item[0];
18
                r = item[1];
19
            }
20
        }
21

22
        res.push_back({l,r});
23
        return res;
24
    }
25
};