LeetCode - 最小堆和最大堆 - 《基础知识》

703.数据流中的第K大元素（easy）

设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。

你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第K大的元素。
解法

动态维护一个最小堆，size为k，每次返还他的top数值。

class KthLargest {
  int K;
  priority_queue<int, vector<int>, greater<int>> pq;
public:
  KthLargest(int k, vector<int>& nums) {
      for (int n : nums) {
          pq.push(n);
          if (pq.size() > k) pq.pop();
      }       
      K = k;
  }
  int add(int val) {
      pq.push(val);
      if (pq.size() > K) pq.pop();
      return pq.top();
  }
};

239.滑动窗口最大值(hard)

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。<br />   解法:<br />   使用deque双项队列解决<br />   构建一个k size大小的最大堆，动态维护，难点：如何把不在区域范围内的数字移除<br />我声明了一个变量 deque，用于存储下标。这个变量有以下 特点:

变量的最前端（也就是 window.front()）是此次遍历的最大值的下标
当我们遇到新的数时，将新的数和双项队列的末尾（也就是window.back()）比较，如果末尾比新数小，则把末尾扔掉，直到该队列的末尾比新数大或者队列为空的时候才停止，做法有点像使用栈进行括号匹配。

双项队列中的所有值都要在窗口范围内

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
      vector<int> res;
      if(k == 0) return res;
      deque<int> window;   //双端队列，从队头到队尾 依次存 窗口内最大元素的index ~ 最小元素的index
      int right = 0;
      while(right < nums.size()){   //后续，窗口每右移一次，都会产生一个最大值[队列头位置的元素]
          if(!window.empty() && window.front() <= right - k){   //队头不在窗口范围内
              window.pop_front();
          }
          while(!window.empty() && nums[right] > nums[window.back()]){   //待入队元素比队尾元素大
              window.pop_back();
          }
          window.push_back(right);
          right++;
          if(right >= k) res.push_back(nums[window.front()]);
      }
      return res;
  }

最小堆和最大堆

703.数据流中的第K大元素（easy）

239.滑动窗口最大值(hard)

更多算法题训练