Readme

1950.Maximum-of-Minimum-Values-in-All-Subarrays

首先我们要有一个意识：如果size变大，那么答案就会单调变小。这是因为size越大的滑窗，就越容易包含更多较小元素，使得subarray的最小值会变得越小。最终的答案也会越小。

于是我们第一个考虑的是，当size=1时答案是什么？显然答案就是数组里的最大值M1。因为M1独自作为一个subarray时，它就是该subarray的最小值。再考虑到它又是全局最大的值，那么它本身就是答案。

那么如果size=2的时候呢？显然答案肯定不会再是刚才的最大值M1了，因为长度为2的滑窗包含M1时，滑窗内必然还有另一个元素比它小。那么根据单调性，我们接下来要查验答案是否为全局的第二大值M2呢？那就取决于M2是否会是某个长度为2的滑窗的最小值。显然，只要M2的左边或右边是M1，那么就存在一个以M2为最小值的、长度为2的滑窗，此时考虑到它又是全局第二大值（M1已经被排除），所以M2就是答案。反之，如果M2的左右两边都是更小的元素，那么M2就不是任何subarray的最小值，我们就继续考察答案是否是全局的第三大元素M3。以此类推，直到找到最大的M满足条件。

至此，我们已经知道规律，对于指定滑窗长度L，要判断某个元素M是否可能为答案，那么先决条件就看：是否存在包含M的、长度为L的滑窗，里面的元素都大于等于M。解决方案是提前用单调栈处理，得到该元素i的prevSmallerElement和nextSmallerElement的位置j与k。如果k-j-1>=L，那么说明存在该长度的滑窗使得内部的所有元素都大于等于M。

考虑到无论L如何变化，我们对于M的探索总是单调地从大到小逐一考察，所以核心代码的时间复杂度其实就是o(N)。当然，为了得到M的降序，还需要额外Nlog(N)的时间。