-
BingoPython：class Solution: # @param {integer[]} nums # @param {integer} k # @return {integer[]} def maxSlidingWindow(self, nums, k): dq = collections.deque() ans = [] for i in range(len(nums)): while dq and nums[dq[-1]] <= nums[i]: dq.pop() dq.append(i) if dq[0] == i - k: dq.popleft() if i >= k - 1: ans.append(nums[dq[0]]) return ans -
BingoC++：
class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> res; deque<int> q; for (int i = 0; i < nums.size(); ++i) { if (!q.empty() && q.front() == i - k) q.pop_front(); while (!q.empty() && nums[q.back()] < nums[i]) q.pop_back(); q.push_back(i); if (i >= k - 1) res.push_back(nums[q.front()]); } return res; } }; -
BingoJava：
public static int[] slidingWindowMax(final int[] in, final int w) { final int[] max_left = new int[in.length]; final int[] max_right = new int[in.length]; max_left[0] = in[0]; max_right[in.length - 1] = in[in.length - 1]; for (int i = 1; i < in.length; i++) { max_left[i] = (i % w == 0) ? in[i] : Math.max(max_left[i - 1], in[i]); final int j = in.length - i - 1; max_right[j] = (j % w == 0) ? in[j] : Math.max(max_right[j + 1], in[j]); } final int[] sliding_max = new int[in.length - w + 1]; for (int i = 0, j = 0; i + w <= in.length; i++) { sliding_max[j++] = Math.max(max_right[i], max_left[i + w - 1]); } return sliding_max; } -
原题： https://leetcode.com/problems/sliding-window-maximum/description/
题意： 给定一个数组，一个大小为k的滑动窗口从数组的最左端向最右端移动。你只可以看到窗口中的k个数字。每一次窗口向右边移动一步。
约定：（1）可以假设k总是有效的，也就是说：1 ≤ k ≤ 输入数组的大小，并且数组非空。
例子：
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]
标签： sliding、window、窗口、maximum、左端、面试
猜你感兴趣的圈子：
