题目描述：
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
Window position Max
--------------- -----
[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
Therefore, return the max sliding window as [3,3,5,5,6,7].
Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.
就是在一个数组中，存在一个长度为k的窗口，每次把这个窗口向后移动1个单元，把最大值取出放入list，直到窗口右端到达数组末尾为止，把最大值的数组list返回。
思路：
1.本题主要是需要使用1个list来表达窗口，在首位移除，末端添加。
2.为了优化性能，可以维护1个maxIndex变量来减小最大值的计算次数。当窗口发生移动时，假设index表示窗口的末尾位置，则：
a.如果首位移除的是maxIndex，则重新计算最大值并更新maxIndex
b.如果首位移除的不是maxIndex，则只需比较nums[maxIndex]与nums[index]即可，更新maxIndex
实现代码：
public class Solution {
public int[] MaxSlidingWindow(int[] nums, int k) {
if(nums.Length == 0){
return new int[0];
}
if(k > nums.Length - 1){
return new int[]{nums.Max()};
}
var result = new List
();
var window = new List
(); var maxIndex = 0; for(var i = 0;i < k; i++){ window.Add(nums[i]); if(nums[maxIndex] < nums[i]){ maxIndex = i; } } result.Add(nums[maxIndex]); var right = k; while(right < nums.Length){ window.RemoveAt(0); window.Add(nums[right]); if(right - k == maxIndex){ maxIndex = CalcMaxIndex(right-k+1, k, nums); }else{ if(nums[right] > nums[maxIndex]){ maxIndex = right; } } result.Add(nums[maxIndex]); right ++; } return result.ToArray(); } private int CalcMaxIndex(int left, int k, int[] nums){ var maxIndex = left ; for(var j = left ;j < left + k; j++){ if(nums[j] > nums[maxIndex]){ maxIndex = j; } } return maxIndex; } }
?
|