AlgoPressAppearance
0239-滑动窗口最大值
https://leetcode.cn/problems/sliding-window-maximum
给你一个整数数组 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]
提示：
1 <= nums.length <= 105 -104<= nums[i] <= 104 1 <= k <= nums.length
思路：双端队列
使用一个双端队列储存当前窗口的最大值，当滑动窗口移动时，新的输入加入，从后面往前检查，删除窗口中小于当前树的数字。
然后加入当前的数字。 队列中储存的是索引，当滑动窗口移动时，前面的索引出街后，从队列中移除。
注意：从开始就添加 maxQueue 当窗口满足条件时输出队列的 maxValue 注意移除出界值的坐标
参考代码
csharp
public class Solution {
public int[] MaxSlidingWindow(int[] nums, int k) {
int n = nums.Length;
LinkedList<int> maxQueue = new LinkedList<int>();
List<int> result = new List<int>();
for(int i=0; i<n; i++){
while(maxQueue.Count > 0 && nums[maxQueue.Last.Value] < nums[i] ){
maxQueue.RemoveLast();
}
maxQueue.AddLast(i);
//移除出界的数字
if(maxQueue.First.Value <= i-k){
//Console.WriteLine("remove {0} at i={1}",maxQueue.First.Value,i);
maxQueue.RemoveFirst();
}
//满足窗口长度就开始计数
if(i>=k-1){
result.Add(nums[maxQueue.First.Value]);
}
}
return result.ToArray();
}
}
思路2：优先队列
使用优先队列，加入的数值中