【算法2-2】常见优化技巧

对应进阶篇第 1 章。 评价算法的标准，除了正确性以外，最重要的就是程序的运行效率是否足够高，是否可以在限定的时间内处理完指定的数据。在“暴力枚举”一章中介绍了可以通过剔除无效操作来提升算法效率。除此之外，还可以用“单调性”和“空间换时间”来优化时间复杂度。将这两种思想结合，产生了单调栈和单调队列等工具。 这些技巧可以帮助我们排除无效选项，在一定范围内保持单调性，常常可以将一些问题求解的时间复杂度降到$O(n)$，因此称为线性时间复杂度优化。