原题 链接
条件:
注意到:随着子数组长度的增加,s(min)即子数组最小值会不变或者减小。可以用反证法证明这一
点,此处略。这个性质意味着如果有长度为L1的子数组最小值大于val,那么我们一定可以找到任意
的长度为L (L <= L1)且最小值大于val的子数组。
思路:
我们不是直接求出对于任一长度为L的子数组的最大min(s),而是对于每一个nums[i],以下标i开始往两边寻找,能维持最小值为nums[i]的最大子数组长度。这个可以通过单调栈来处理,寻找对于nums[i]左右两边第一个小于nums[i]的数记录其下标,然后求出对于每个i所能维持的最大长度存入rec[i]中。
在求出这一步之后,还要做一个简单处理,就是改变rec[i]的含义,我们用rec[i]表示所形成子数组大于等于nums[i]的最大长度。
之后考虑如何回答询问,对于val , mn, mx 这样一组问询,我们首先查找第一个大于val的nums[i],如果没有比val大的数,回答否,如果有,根据rec[i]的含义,直接判断rec[i] 是否不小于mn,是则可以找到一个长度大于mn且min(s)大于val的子数组,我们预先将nums[i] 和下标i放进pair里,然后排序,所以回答的时候二分查找即可。
1 | using i64 = long long; |