尺取法

· · 个人记录

尺取法：

顾名思义，像尺⼦⼀样取⼀段，借⽤挑战书上⾯的话说，尺取法通常是对数组保存⼀对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。尺取法⽐直接暴⼒枚举区间效率⾼很多，尤其是数据量⼤的时候，所以说尺取法是⼀种⾼效的枚举区间的⽅法，是⼀种技巧，⼀般⽤于求取有⼀定限制的区间个数或最短的区间等等。当然任何技巧都存在其不⾜的地⽅，有些情况下尺取法不可⾏，⽆法得出正确答案，所以要先判断是否可以使⽤尺取法再进⾏计算。使⽤尺取法时应清楚以下四点：1、 什么情况下能使⽤尺取法? 2、何时推进区间的端点？ 3、如何推进区间的端点？ 4、何时结束区间的枚举？尺取法通常适⽤于选取区间有⼀定规律，或者说所选取的区间有⼀定的变化趋势的情况，通俗地说，在对所选取区间进⾏判断之后，我们可以明确如何进⼀步有⽅向地推进区间端点以求解满⾜条件的区间，如果已经判断了⽬前所选取的区间，但却⽆法确定所要求解的区间如何进⼀步得到根据其端点得到，那么尺取法便是不可⾏的。⾸先，明确题⽬所需要求解的量之后，区间左右端点⼀般从最整个数组的起点开始，之后判断区间是否符合条件在根据实际情况变化区间的端点求解答案。