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

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

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

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

2

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

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

};

1

c++

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) 
    {
        vector<int> res;
        if(nums.empty()) return {};
        else if(k == 1) return nums;
        else 
        {
            
            deque<int> dq1;
            deque<int> dq2;
            for(size_t i=0;i<k;++i)
            {
                dq1.push_back(nums[i]);
                if(dq2.empty()) dq2.push_back(nums[i]);
                else
                {
                    while(!dq2.empty() && dq2.back() < nums[i])
                    {
                        dq2.pop_back();
                    }
                    dq2.push_back(nums[i]); 
                }
            }

            res.push_back(dq2.front());

            for(size_t i=k;i<nums.size();++i)
            {
                if(dq1.front() == dq2.front())
                {
                    dq2.pop_front();
                }
                dq1.pop_front();
                dq1.push_back(nums[i]);
         
                while(!dq2.empty() && dq2.back() < nums[i])
                {
                    dq2.pop_back();
                }
                dq2.push_back(nums[i]); 
                res.push_back(dq2.front());
            }
        }
        return res;
    }
};
2

max初始化成0真的好吗,窗口内都是负数呢

1

你的max应该在每一次窗口时重新赋值,max的值也最好使用INT_MIN,因为可能一个窗口里全是负数

1

谢谢,我试试

1
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        int max=0;
        for(int s=0;s+k<nums.size();++s)
        {
            for(int j=s;j<=s+k;++j)
            {
                if(nums[j]>=max)
                    max=nums[j];   
            }

            res.push_back(max);
        }
        return res;
    }
};

请问我这个算法错哪了,看不出来!

1

priority_queue+延迟删除也不错

1