LeetCode -- Sliding Window Maximum

LeetCode -- Sliding Window Maximum

題目描述：


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;
}
    
}