Day10 | Part3

约 176 个字 31 行代码 预计阅读时间 1 分钟

239.滑动窗口最大值

利用 单调队列 即队列中元素单调递减/递增(利用deque实现) →动图参考

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> res;
    deque<int> dq; // 双端队列
    int i = 0, j = 0;
    while( j < nums.size() ) {
        while(!dq.empty() && nums[j] > dq.back()) dq.pop_back();
        if (j - i + 1 < k) j ++;
        else if (j - i + 1 == k) {
            res.push_back(dq.front());
            if (dq.front() == nums[i]) dq.pop_front();
            i ++, j ++;
        }
    }
    return res;
}

347.前K个高频元素

利用小根堆,每次将最小的弹出,剩下的就是前k个最大的

• C++中priority_queue(优先队列)即是堆,只能队头取元素,队尾添元素(默认大根队)
• 利用map对出现的频率进行排序

  vector<int> topKFrequent(vector<int>& nums, int k) {
      vector<int> res;
      unordered_map<int, int> map; //记录<nums[i],对应次数>
      priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
      // greater代表从小到大插入元素
      for(auto i : nums) map[i] ++;
      for (auto i : map) {
          pq.push({i.second, i.first});
          if (pq.size() > k) pq.pop();
      }
      while (k --) {
          res.push_back(pq.top().second);
          pq.pop();
      }
      return res;
  }
  

Q: C++ 中栈里面的元素在内存中是连续分布的么？

• 栈是容器适配器，底层容器使用不同的容器，导致栈内数据在内存中不一定是连续分布的
• 默认底层容器是deque，即不连续的

颜色主题调整

red pink purple indigo blue cyan teal green lime orange brown grey black white

快来和我聊天~

可以的话请给我赞和 star喔~    => 

评论