AlgoPressAppearance
59-I-滑动窗口的最大值
题目描述
https://leetcode.cn/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof
给定一个数组 nums 和滑动窗口的大小 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
提示：
你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤输入数组的大小。
注意：本题与主站 239 题相同：https://leetcode.cn/problems/sliding-window-maximum/
思路分析
使用 LinkedList 模拟双端队列 滑动窗口 [left..right] 如果 nums[left] < nums[right] 那么 nums[left] 永远不可能为最大值，因为 right 在left后面被移除 每次遍历到一个数的时候，先加入list，然后判断前面的值是不是小于当前的数，如果是，则循环移除(removeLast) 【大根堆】 ，这样第一个数就是当前滑动窗口中的最大值。
当遍历到 i - 窗口大小前面的索引时，也移除该索引，因为他在窗口外了。
实现代码
csharp
public class Solution {
public int[] MaxSlidingWindow(int[] nums, int k) {
if(nums.Length == 0 || k == 0){
return new int[]{};
}
int[] ans = new int[nums.Length - k + 1];
LinkedList<int> list = new LinkedList<int>();
//加入初始队列
for(int i=0; i<k;i++){
//加入queue的时候，如果发现前面的数小于最后的数，则移除
while(list.Count > 0 && nums[list.Last.Value] <= nums[i]){
list.RemoveLast();
}
list.AddLast(i);
}
//队列中的第一个数永远是最大值
ans[0] = nums[list.First.Value];
for(int i=k; i<nums.Length; i++){
while( (list.Count > 0 && nums[list.Last.Value] <= nums[i])){
list.RemoveLast();
}
list.AddLast(i);
if(list.First.Value == i-k){
list.RemoveFirst();
}
ans[i-k+1] = nums[list.First.Value];
}
return ans;
}
}