OJ刷题准则，拒绝暴力求解

写在前面：大家好！我是【AI 菌】，一枚爱弹吉他的程序员。我热爱AI、热爱分享、热爱开源！ 这博客是我对学习的一点总结与记录。如果您也对 深度学习、机器视觉、算法、Python、C++ 感兴趣，可以关注我的动态，我们一起学习，一起进步~
我的博客地址为：【AI 菌】的博客
我的Github项目地址是：【AI 菌】的Github

时间和空间复杂度是算法中很重要的概念，同时在面试中也会经常要求分析代码的时空复杂度。因此，我们在OJ平台上做每一道题时，在思考算法时也应该大致分析一下自己代码的时空复杂度，切勿盲目暴力求解。

在常见的OJ 平台上的题库中，一般都会附带数据范围，为了避免超时，在做题时也要养成习惯：通过题目给出数据范围，估测可允许的最大时间与空间复杂度量级，进而选择对应的可用算法。

在估算时，我们可以按照以下的准则：

在大部分 C++/Java 平台上，计算机 1s 内的处理次数大约为 10^7 - 10^8，Python 由于相对较慢，大约为 10^6 -10^7，而大部分OJ平台的时限都在 1s - 10s 左右，而对于一些题目来说，时限会更短。

下面举个实际的例子：

题目描述：
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
要求：返回滑动窗口中的最大值。

示例 ：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]

提示：
1 <= nums.length <= 10e5
-10e4 <= nums[i] <= 10e4
1 <= k <= nums.length

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
 

注：题目来源力扣

对于本题，在设计算法的时候，我们必须得考虑提示部分的数据范围：

• 确定主要考量对象。由于我们主要对数组nums进行操作，所以nums.length是重要的考量对象。
• 按范围最大值去估算耗时，在这里取nums.length的最大值10e5。
• 设计相应时间复杂度的算法。想想如果设计的算法时间复杂度为O(n^2)，那么该程序一次最多需要处理10e10次，这将大大超过时限。所以对于本题，应该设计时间复杂度为O(n)或者O(nlogn)的算法。

由于水平有限，博客中难免会有一些错误，有纰漏之处恳请各位大佬不吝赐教！

推荐文章

程序员面试必备的八大数据结构

文章来源: ai-wx.blog.csdn.net，作者：AI 菌，版权归原作者所有，如需转载，请联系作者。

原文链接：ai-wx.blog.csdn.net/article/details/114624959