我掐指一算，这个月估计是双指针滑动窗口月了，到月底我就会做滑动窗口的题了
LeetCode上滑动窗口中位数，困难难度，记录下解题思路
传入一个数组，以及窗口大小k，题意的中位数是窗口内的数是有序排列的有序排列，如果k为单数，那么中位数就是中间那个数字，如果k为双数，那么就是中间两位的平均数
需要做到下面几件事情：
- 实现窗口滑动，每次滑动都要移出移入数据
- 每次移入移出之后要保证k的有序排列
- 根据k来取中位数
- 将每次的中位数放入一个数组，最后返回整个数组
窗口滑动实现
这个程序的范围是由right决定，当right到达数组最后一位，那么循环就结
while(right<nums.length) {
right++
}
在循环的时候需要进行几个判断
- 什么时候确定窗口的长度达到上限
- 窗口移动的实现
while(right<nums.length) {
// 窗口滑动的范围是，当窗口的左侧到nums的最后一位
if(right-left+1 < k) {
} else if(right-left+1 === k) {
// 当窗口大小正好等于k的时候
} else {
// 当窗口大小比k大的情况，就要移出数据以及传入数据
left++
}
right++
}
窗口大小的判断是根据right - left + 1和传入的k进行对比，right - left + 1就是当前窗口的长度，+1是因为当left和right都为0的时候，窗口长度为1
通过最后的right++来实现窗口的扩展，当right - left + 1 > k的时候进入最后一个判断，可以维护窗口的大小始终为k
移入移出数据
通过两个独立函数来实现移入移出
移入数据
// w为删除元素后数组，k为要添加的数组
// 添加完成后要维护数组的有序性
let windowSort = function (w,t) {
// 将k放入w，并且对w进行排序
w.push(t)
w.sort((a,b) => {return a - b})
return w
}
每次传入后都通过sort方法维护窗口数组的有序
移出数据
// 删除window中的对应数据
let windowDelete = function(w,t) {
// 查找t在w中的位置
let index = w.indexOf(t)
// 删除w中对应位置的数据
w.splice(index,1)
return w
}
因为窗口的内部顺序是递增的，但是移出的数据不能确定是在窗口内的哪一个，所以用indexOf来查找对应的位置，并且使用splice删除对应数据
取中位数
每次根据k来获取window内的中位数，k有可能是单数和双数
要获取k对应的中间数index，用k/2向下取整获得，假设k为单数，那么index就是中间的位置，如果k为双数，那么就要取index和index-1的数来求平均值
// 查找window的中位数
let find = function (w,k) {
// 对应的中间index
// k/2向下取整，可以得到对应k中间应该取什么数
// 例如k=3 此时index = 1 k=6此时index=3
let index = Math.floor(k/2)
let num = 0
if(k%2===0) {
// k是双数，取index和index-1的数来取平均值
num = (w[index]+w[index-1]) / 2
} else {
// k是单数，直接取index对应的数
num = w[index]
}
return num
}
// w为删除元素后数组，k为要添加的数组
// 添加完成后要维护数组的有序性
let windowSort = function (w,t) {
// 将k放入w，并且对w进行排序
w.push(t)
w.sort((a,b) => {return a - b})
return w
}
// 删除window中的对应数据
let windowDelete = function(w,t) {
// 查找t在w中的位置
let index = w.indexOf(t)
// 删除w中对应位置的数据
w.splice(index,1)
return w
}
// 查找window的中位数
let find = function (w,k) {
// 对应的中间index
// k/2向下取整，可以得到对应k中间应该取什么数
// 例如k=3 此时index = 1 k=6此时index=3
let index = Math.floor(k/2)
let num = 0
if(k%2===0) {
// k是双数，取index和index-1的数来取平均值
num = (w[index]+w[index-1]) / 2
} else {
// k是单数，直接取index对应的数
num = w[index]
}
return num
}
var medianSlidingWindow = function(nums, k) {
// 用于返回的结果
let res = []
// 用于定义窗口
let right = 0
let left = 0
// 对应的窗口数组
let window = []
while(right<nums.length) {
// 窗口滑动的范围是，当窗口的左侧到nums的最后一位
// 判断当前窗口大小和k的关系
if(right-left+1 < k) {
// 这个情况是窗口还没有到达k的时候
// 传入当前left的数据，并且维护窗口内数据递增
window = windowSort(window,nums[right])
} else if(right-left+1 === k) {
// 当窗口大小正好等于k的时候
window = windowSort(window,nums[right])
// console.log(window);
res.push(find(window,k))
} else {
// 当窗口大小比k大的情况，就要移出数据以及传入数据
// 删除window中对应的nums[left]
window =windowDelete(window,nums[left])
// 然后left要右移
left++
window = windowSort(window,nums[right])
// console.log(window);
res.push(find(window,k))
}
right++
}
// console.log(res);
return res
};
