烦请老师指教，sliding windows maximum
来源：3-8 在滑动窗口中做记录 Longest Substring Without Repeating Characters
慕慕9414451
2017-11-17
老师，求滑动窗口最大值这个问题。我的代码如下，是调用了另外一个函数。我觉得是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;
}
};
1回答
-
leetcode中有些问题，尤其是编号比较小的问题，测试数据集会比较弱，复杂度高的算法也会通过。所以leetcode相对比较简单。不过我观察leetcode中编号比较高的新题，测试数据越来越强了。但整体无论从问题本身还是对优化程度的要求都比程序设计竞赛简单。但其实本身面试算法也比程序设计竞赛简单很多：）
112017-11-18
相似问题