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

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

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

暴力大法

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

构建单调队列法:

class Solution { private: /* 定义一个类实现单调队列 */ class Myqueue { public: /* 使用双端队列实现 */ deque<int> que; /* 实现pop函数只是为了每次窗口移动移除前面已经走过的元素 */ void pop(int value) { if(!que.empty() && value == que.front())// 这里每次移除一个元素所以用if不用while que.pop_front(); } /* 实现一个push为了让队列头部始终是最大值,是一个有序队列 */ void push(int value) { while(!que.empty() && value > que.back()) que.pop_back(); que.push_back(value); } /* 实现front为了返回最大值 */ int front() { return que.front(); } }; public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { /* 定义一个单调队列 */ Myqueue que; /* 定义个存储结果的vector */ vector<int> result; /* 首先先将前k个元素入队列 */ for(int i = 0; i < k; i++) que.push(nums[i]); /* 获取窗口没有移动的时候里面的最大值 */ result.push_back(que.front()); /* 让窗口滚动起来 */ for(int i = k; i < nums.size(); i++) { /* pop来了移除前面第一个元素模拟窗口滚动 */ que.pop(nums[i-k]); /* 让新进窗口的元素进队列 */ que.push(nums[i]); /* 获取当前窗口的最大值 */ result.push_back(que.front()); } return result; } };
3

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

};

3

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

3

python3

class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: if len(nums) == 0: return [] L = [] for i in range(len(nums) - k + 1): if i == 0: ans = max(nums[i:i+k]) else: ans = max(ans, nums[i+k-1]) if ans in nums[i:i+k] else max(nums[i:i+k]) L.append(ans) return L
2

代码2

class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { int n = nums.size(); deque<int> dq; vector<int> ans; for (int i = 0; i < n; i ++ ) { if (dq.size() && dq.front() < i - k + 1) dq.pop_front(); while (dq.size() && nums[dq.back()] <= nums[i]) dq.pop_back(); dq.push_back(i); if (i - k + 1 >= 0) ans.push_back(nums[dq.front()]); } return ans; } };
2

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

2

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

2

大家看那一下我的时间复杂度

class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: #我的思路是使用队列,先进先出的方式 # 创建一个列表盛放最大值 maxList=[] #先判断链表长度 if len(nums)<k:return #第一步让队列充满k个元素 d1=deque() # 设置一个max(初始值定为list的第一个值) max = nums[0] for i in range(k): d1.append(nums[i]) #设置一个方法:求队列最大值 def countListMaxValue(de:deque)->int: #定一个起始最大值 max=de[0] for i in de: if max<i: max=i return max firstValue=countListMaxValue(d1) #第一个值 maxList.append(firstValue) #第二步队列走出一个,走进一个的方式 while k<len(nums): d1.popleft() d1.append(nums[k]) maxValue=countListMaxValue(d1) maxList.append(maxValue) k=k+1 return maxList
1