13.滑动窗口

3. 无重复字符的最长子串

class Solution {
public:
  int lengthOfLongestSubstring(string s) {
    if (s.empty()) {
      return 0;
    }
    unordered_set<char> cache;
    int max_t = 0, left = 0;
    for (int i = 0; i < s.size(); i++) {
      while (cache.find(s[i]) != cache.end()) {
        cache.erase(s[left]);
        left += 1;
      }
      max_t = max(max_t, i - left + 1);
      cache.insert(s[i]);
    }
    return max_t;
  }
};

239. 滑动窗口最大值

vector<int> maxSlidingWindow(vector<int> &nums, int k) {
    priority_queue<pair<int, int>> queue;
    int size = nums.size();
    for (int i = 0; i < k; i++) {
      queue.emplace(nums[i], i);
    }
    vector<int> ans = {queue.top().first};
    // 1,3,-1,-3,5,3,6,7
    for (int i = k; i < size; i++) {
      queue.emplace(nums[i], i);
        //注意 <= 的判断条件，很容易只写成 <
      while (queue.top().second <= i - k) {
        queue.pop();
      }
      ans.emplace_back(queue.top().first);
    }
    return ans;
  }