烦请老师指教，sliding windows maximum

Question

老师，求滑动窗口最大值这个问题。我的代码如下，是调用了另外一个函数。我觉得是O(n2)级别的算法，为什么还accepted了呢？

class Solution {

public:

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {

        

        vector<int> res;

        int n=nums.size();

        if(n==0)

            return res;

        

        for(int i=0;i<=n-k;i++){

            int max=findmax(nums,i,i+k-1);

            res.push_back(max);

        }

        

        return res;

    }

    

    int findmax(vector<int> &nums,int l,int r){

        int max=nums[l];

        for(int i=l+1;i<=r;i++){

            if(nums[i]>max)

                max=nums[i];

        }

        

        return max;

    }

};

Answer 1

liuyubobobo 2017-11-18 01:58:21

leetcode中有些问题，尤其是编号比较小的问题，测试数据集会比较弱，复杂度高的算法也会通过。所以leetcode相对比较简单。不过我观察leetcode中编号比较高的新题，测试数据越来越强了。但整体无论从问题本身还是对优化程度的要求都比程序设计竞赛简单。但其实本身面试算法也比程序设计竞赛简单很多：）

• 提问者 慕慕9414451 #1

  深深感受到了竞赛对思维锻炼的好处。谢谢老师