239. 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1
输出：[1]
示例 3：
输入：nums = [1,-1], k = 1
输出：[1,-1]
示例 4：
输入：nums = [9,11], k = 2
输出：[11]
示例 5：
输入：nums = [4,-2], k = 2
输出：[4]
思路分析(明日完善)
单调队列的使用
这道题不复杂，难点在于如何在 O(1) 时间算出每个「窗口」中的最大值，使得整个算法在线性时间完成。就需要「单调队列」这种特殊的数据结构来辅助了。
C++普通队列:
class Queue {
void push(int n);
// 或 enqueue，在队尾加入元素 n
void pop();
// 或 dequeue，删除队头元素
}
单调队列:
class MonotonicQueue {
// 在队尾添加元素 n
void push(int n);
// 返回当前队列中的最大值
int max();
// 队头元素如果是 n，删除它
void pop(int n);
}
实现单调队列数据结构
单调队列的 push 方法依然在队尾添加元素，但是要把前面比新元素小的元素都删掉; 要用到双端队列:deque
class MonotonicQueue {
private:
deque<int> data;
public:
void push(int n) {
while (!data.empty() && data.back() < n)
data.pop_back();
data.push_back(n);
}
};
加入数字的大小代表人的体重，把前面体重不足的都压扁了，直到遇到更大的量级才停住。
如果每个元素被加入时都这样操作，最终单调队列中的元素大小就会保持一个单调递减的顺序，因此我们的 max() API 可以可以这样写：
int max() {
return data.front();
}
pop() API 在队头删除元素 n，也很好写：
void pop(int n) {
if (!data.empty() && data.front() == n)
data.pop_front();
}
之所以要判断 data.front() == n 是因为我们想删除的队头元素 n 可能已经被「压扁」了，这时候就不用删除了：
至此，单调队列设计完毕.
参考代码
class MonotonicQueue {
private:
deque<int> Q;
public:
void push(int n) {
while(!Q.empty() && Q.back() < n) { //把 < n的元素都压扁
Q.pop_back();//从后面弹出..
}
Q.push_back(n);
}
int max() {
return Q.front();//最大的便是对头元素
}
void pop(int n) {
if(!Q.empty()&& Q.front()==n) { //如果窗口移除的元素= 最大值, 则单调队列中删除该元素.
Q.pop_front();//从前面弹出.
}
}
};
//单调队列的使用
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MonotonicQueue window;
vector<int> res;
for(int i = 0;i < nums.size();i++){
if(i < k-1){//先填满窗口的k-1
window.push(nums[i]);
}else{//窗口向前移动
window.push(nums[i]); // 窗口变成k-1 ==>右边界右移动
res.push_back(window.max()); //弹出最大的元素
window.pop(num[i-k+1]);//删除最左边的元素.==> 左边界右移动
}
}
return res;
}
复杂度分析
- 时间复杂度: O ( N ) O(N) O(N): 因为每个元素只被push和pop了一次.
347. 前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
思路分析
这个题考察内容:
- 要统计元素出现频率==>使用map
- 对频率排序=>使用优先队列
- 找出前K个高频元素
priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。
什么是堆呢?
堆是一颗完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。
如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。
所以我们可以用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。(当然如果是大根堆,那么弹出前k个元素就行.)
参考代码
//定义优先队列的排序规则(优先队列和常规的排序规则(如快排)正好相反
class mycomparison {
public:
bool operator(const pair<int,int>& l,const pair<int,int>& r) {
return l.second > r.second;
}
};
class Solution {
public:
//小顶堆
vector<int> topKFrequent(vector<int>& nums, int k) {
//要统计元素出现的频率
unordered_map<int,int> map;
for(int i = 0;i < nums.size();i++){
map[nums[i]]++;
}
//对频率排序
//定义一个小根堆,大小为k
priority_queue<pair<int,int>,vector<pair<int,int>>, mycomparison> Q;
//用固定大小为k的小根堆,扫到所有频率的数值
for(unordered_map<int,int>::iterator it = map.begin(); it!= map.end(); it++){
Q.push(*it);
if(Q.size()>k){
Q.pop();
}
}
//找出前k个高频元素,因为小根堆先弹出的是最小的.
vector<int> res(k);
for(int i = k-1; i>=0;i--){
res[i] = Q.top().first;
Q.pop();
}
return res;
}
};
注:pair可看做map的一个子元素模板,可以对map进行赋值,初始化等操作.