单调队列问题-LeetCode 239、169（单调队列，Boyer-Moore投票法）
单调队列问题-LeetCode 239、169（单调队列，Boyer-Moore投票法）
单调队列：LeetCode #239 169
1
编程题
【LeetCode #239】滑动窗口的最大值
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回滑动窗口中的最大值。
示例: 输入: 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
解题思路：
下面有两种形式的实现，但我觉得将单调队列使用类封装更加容易理解，因此可以直接看第二个答案。对于单调队列（实质为单调递减队列）来说，其最大值总是在队列的队首，虽然在push函数中存在有while循环，但是总体来说，单调队列还是可以实现O(N)的复杂度的。
在push函数中，需要将操作数n和队尾循环比较，如果大于队尾，则删除队尾！接着压入操作数n，这样一来就保证了最大值在队列首部，且队列为递减队列！ 在pop函数中，如果队首与操作数相同，则删除堆头，否则不用删除了！因为有可能在push阶段已经删除掉了！
（数端数组）
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int>res;
deque<int>s;
int len=nums.size();
if (len <= 0 || k<=0 || k > len)return res;
for (int i = 0;i < len; i++)
{
while (!s.empty() && nums[s.back()] <= nums[i])
s.pop_back();
while (!s.empty() && i - s.front() + 1> k) //最大值已不在窗口中
s.pop_front();
s.push_back(i);
if (i + 1 >= k) //当滑动窗口首地址i大于等于size时才开始写入窗口最大值
res.push_back(nums[s.front()]);
}
return res;
}
};（单调队列使用类封装）
class Solution {
public:
class MaxDeque{
public:
deque<int> nums;
void push(int n){
while(!nums.empty() && nums.back() < n){
nums.pop_back();
}
nums.push_back(n);
}
int max(){
return nums.front();
}
void pop(int n){
if(!nums.empty() && n == nums.front()){
nums.pop_front();
}
}
};
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MaxDeque windows;
vector<int> res;
for(int i = 0; i < nums.size(); i++){
if(i < k-1){
windows.push(nums[i]);
}else{
windows.push(nums[i]);
res.push_back(windows.max());
windows.pop(nums[i-k+1]);
}
}
return res;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sliding-window-maximum
【LeetCode #169】求众数
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1: 输入: [3,2,3] 输出: 3
解题思路：
由于题目说众数为个数大于n/2的数，因此： 第一个思路十分简单，将整个数组排序后，众数那个数一定在数组的中间位置，直接返回就好了！ 第二个思路不太好想，Boyer-Moore算法： 假设第一个数为众数，令众数为1， 其他数为-1，因此维护一个计数器，碰到一个数为候选众数，就将计数器加一，否则就减一，并把下一个数当做候选的众数。 其时间复杂度为O(n)，空间复杂度为O(1).
class Solution {
public:
int majorityElement(vector<int>& nums) {
if(nums.size() == 1) return nums[0];
sort(nums.begin(), nums.end());
return nums[nums.size()/2];
}
};（Boyer-Moore 投票算法）
class Solution {
public:
int majorityElement(vector<int>& nums) {
int res = 0, cnt = 0;
for(int i = 0;i < nums.size();i++){
if(cnt == 0){
res = nums[i];
cnt ++;
}else{
res == nums[i] ? ++cnt : --cnt;
}
}
return res;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/majority-element
腾讯云开发者
