解题思考：

1. 根据数据规模，考虑可以使用什么算法？
2. 不急着动手，根据题意，理清大致流程。

• 前缀和+线性dp
• 贪心(常先排序)+优先队列
• 二分：二分下标，二分答案，其他有序的都可以作为二分条件。
• 单调栈，单调队列
• 二分套二分，二分套双指针

看到一道题，第一反应想到用什么方法解题？

• 若dfs超时，可考虑动态规划，剪枝，可考虑是否可以二分答案。
• 递归改动态规划，几个可变参数维护几维数组
• unordered_mp ：哈希，key-val 的类型可以有很多种，key也可以是指针。

  数据规模跟算法时间复杂度的对应关系

  | Input Size | Complexity | | —- | —- | | 50000 | O (n) | | 20000 | O (n logn) | | 1000 | O (n ^ 2) | | 30 | O (n ^ 4) | | 20 | O (2 ^ n) |

各算法对应的最坏时间复杂度

如何判断自己的程序是否会超时： 首先看题目数据的大小， 会给一个数据范围，比如0<N <1000， 接下来看你的程序的代码的语句一共运行多少次， 基本上就是看 循环的层数（一般是看有多少个for嵌套或者while）。N为上面那个范围，要考虑极限数据 就是 N = 1000的情况， 三个for嵌套 就是 1000的三次方 等于10亿 对于这个数量级程序就会超时。

• 程序执行语句次数一般控制在(10^7 -10^8)以下 就不会超时，这个是因为计算机每秒可以运行大概10^8条语句。

双指针，滑动窗口

最多 - 最多 = 恰好
看到最小、最大字眼，想到双指针。

哪些编码方式，影响时间复杂度的

// vector的构造比 pair的耗时。
queue<pair<int, int>> 时间复杂度优于queue<vector<int>>
// new 的操作很耗时，程序代码不能循环new
// unordered_map<pair<int, int>, int> 的方式标记已访问坐标，不如使用数组vector<vector<int>>。
//

二维数组每个点的标识方式

{i, j}
id = i * n + j