讨论/《图解算法数据结构》 - 剑指 Offer 59 - I 题目解析/
《图解算法数据结构》 - 剑指 Offer 59 - I 题目解析
共 17 个回复

实在想不出简单的办法,用了一个贼蠢的 = =

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0) {
            return nums;
        }
        int[] res = new int[nums.length - k + 1];
        int max = nums[0];
        for (int i = 0, count = 0, index = 0; i < nums.length; i++, count++) {
            if (count != 0 && count % k == 0) {
                i = i - k + 1;
                res[index++] = max;
                max = nums[i];
            }
            max = nums[i] >= max ? nums[i] : max;
            if (i == nums.length - 1) {
                res[index++] = max;
            }
        }
        return res;
    }
}
7

我看没有c++版本的双端队列,发上c++的吧

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        if (nums.size()==0 || k==0) return res;
        deque<int> d;
        for (int j=0, i=1-k; j<nums.size(); i++, j++) {
            if (i>0 && d.front()==nums[i-1]) d.pop_front();
            while (!d.empty() && d.back() < nums[j]) d.pop_back();
            d.push_back(nums[j]);
            if (i>=0) res.push_back(d.front());
        }
        return res;

    }
};
3

暴力大法

public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0)
        return new int[]{};
        int arr[] = new int[nums.length-k+1];
        for(int i = 0;i<=nums.length-k;i++){
            int max = nums[i];
            for(int j = i+1;j<k+i;j++){
                if(nums[j]>max){
                    max = nums[j];
                }
            }
            arr[i] = max;
        }
        return arr;
    }
2

用了stack
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
if (nums.size() <= 1)
return nums;
vector<int> maxNums;

    for (int i = 0; i <= nums.size() - k; i++)
    {
        stack<int> numStack;
        for (int j = 0; j < k; j++)
        {
            if (numStack.empty() || nums[i + j] >= numStack.top())
            {
                numStack.push(nums[i + j]);
            }
        }
        maxNums.push_back(numStack.top());
    }
    return maxNums;
}

};

2

priority_queue也不是很简单,每次滑过一个窗口,就要删除一个数,而这个数在哪还要找一番

2

for(int j=s;j<=s+k;++j)这里j<=s+k不能用 <= 要用 <

2

这个单调队列的方法真是有必要实现一遍,基本以后碰到类似的题就用这一种办法搞定了。

1
func maxSlidingWindow(nums []int, k int) []int {
	arry := []int{}
	if len(nums) == 0 {
		return arry
	}

	// 查找第一组最大的
	maxIndex := 0
	for i := 1; i < k; i++ {
		if i >= len(nums) {
			arry = append(arry, nums[maxIndex])
			return arry
		}
		if nums[maxIndex] <= nums[i] {
			maxIndex = i
		}
	}
	arry = append(arry, nums[maxIndex])
	if len(nums) == k {
		return arry
	}

	for i := 1; i < len(nums); i++ {
		if i + k > len(nums) {
			break
		}
		if maxIndex >= i && nums[maxIndex] > nums[i + k - 1] {
		} else if maxIndex >= i && nums[maxIndex] <= nums[i + k - 1] {
			maxIndex = i + k - 1
		} else {
			maxIndex = i
			for j := 1; j < k; j++ {
				if nums[maxIndex] < nums[i + j] {
					maxIndex = i + j
				}
			}
		}
		arry = append(arry, nums[maxIndex])
	}

	return  arry
}
1

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
    int len=nums.length;
    if(len==0) return nums;
    int r=k-1;
    int[] arr=new int[len-k+1];
    int ans=Integer.MIN_VALUE;
    for(int l=0;l<len-k+1;l++){
        for(int i=l;i<k+l;i++){
            ans=Math.max(ans,nums[i]);
        }
        arr[l]=ans;
        ans=Integer.MIN_VALUE;
    }
    return arr;
    }
}
1

直接法

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.size() < 1 || nums.size() < k) return {};
        int maxV = INT_MIN;
        for(int i = 0; i < nums.size() - k + 1; i++) {
            for(int j = i; j < i + k; j++) {
                if(nums[j] > maxV) maxV = nums[j];
            }
            max.push_back(maxV);
            maxV = INT_MIN;         
        }
        return max;
    }
public:
    vector<int> max;
};
1