1950. Maximum of Minimum Values in All Subarrays
ArrayStackMonotonic StackCartesian Tree
Hints
Hint 1
Imagine the array is empty, and each element is coming to its index one by one, starting with the smallest element.
Hint 2
For each coming element nums[i], calculate L and R, the indices of the first smallest elements on the left and the right respectively.
Hint 3
The answer of the queries from 1 to R-L+1 will be at least this element.
Preparing judge…