1. 力扣239-滑动窗口最大值

  • 使用单调队列(双端队列)
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> q;
        for (int i = 0; i < k; i++) {
            while (!q.empty() && nums[i] > nums[q.back()]) 
                q.pop_back();
            q.push_back(i);
        }
        vector<int> ans;
        ans.push_back(nums[q.front()]);
        for (int i = k; i < nums.size(); i++) {
            while (!q.empty() && nums[i] > nums[q.back()]) 
                q.pop_back();
            q.push_back(i);
            while (q.front() <= i - k) q.pop_front();
            ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};
  • 使用优先队列
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        priority_queue<pair<int, int>> q;
        for (int i = 0; i < k; i++) {
            q.push({nums[i], i});
        }
        vector<int> ans;
        ans.push_back(q.top().first);
        for (int i = k; i < nums.size(); i++) {
            q.push({nums[i], i});
            while (q.top().second <= i - k) q.pop();
            ans.push_back(q.top().first);
        }
        return ans;
    }
};

2. 力扣3-无重复字符的最长子串

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> mp;
        int rt = -1, ans = 0;
        for (int i = 0; i < s.size(); i++) {
            if (i) mp.erase(s[i - 1]);
            while (rt + 1 < s.size() && mp.count(s[rt + 1]) == 0) {
                mp[s[rt + 1]] = 1;
                rt++;
            }
            ans = max(ans, rt - i + 1);
        }
        return ans;
    }
};
最后修改:2021 年 03 月 30 日 10 : 13 AM