# 1950. Maximum of Minimum Values in All Subarrays

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 class Solution { public: // Similar to 1950. Maximum of Minimum Values in All Subarrays vector findMaximums(vector& nums) { const int n = nums.size(); vector ans(n); // prevMin[i] := index k s.t. nums[k] is the prev min in nums[:i] vector prevMin(n, -1); // nextMin[i] := index k s.t. nums[k] is the next min in nums[i + 1:] vector nextMin(n, n); stack stack; for (int i = 0; i < n; ++i) { while (!stack.empty() && nums[stack.top()] > nums[i]) { const int index = stack.top(); stack.pop(); nextMin[index] = i; } if (!stack.empty()) prevMin[i] = stack.top(); stack.push(i); } // For each nums[i], let l = nextMin[i] + 1 and r = nextMin[i] - 1. // nums[i] is the minimun in nums[l..r]. // So, the ans[r - l + 1] will be at least nums[i]. for (int i = 0; i < n; ++i) { const int sz = nextMin[i] - prevMin[i] - 1; ans[sz - 1] = max(ans[sz - 1], nums[i]); } // ans[i] should always >= ans[i + 1:]. for (int i = n - 2; i >= 0; --i) ans[i] = max(ans[i], ans[i + 1]); return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 class Solution { // Similar to 1950. Maximum of Minimum Values in All Subarrays public int[] findMaximums(int[] nums) { final int n = nums.length; int[] ans = new int[n]; // prevMin[i] := index k s.t. nums[k] is the prev min in nums[:i] int[] prevMin = new int[n]; // nextMin[i] := index k s.t. nums[k] is the next min in nums[i + 1:] int[] nextMin = new int[n]; Deque stack = new ArrayDeque<>(); Arrays.fill(prevMin, -1); Arrays.fill(nextMin, n); for (int i = 0; i < n; ++i) { while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) { final int index = stack.pop(); nextMin[index] = i; } if (!stack.isEmpty()) prevMin[i] = stack.peek(); stack.push(i); } // For each nums[i], let l = nextMin[i] + 1 and r = nextMin[i] - 1. // nums[i] is the minimun in nums[l..r]. // So, the ans[r - l + 1] will be at least nums[i]. for (int i = 0; i < n; ++i) { final int sz = nextMin[i] - prevMin[i] - 1; ans[sz - 1] = Math.max(ans[sz - 1], nums[i]); } // ans[i] should always >= ans[i + 1:]. for (int i = n - 2; i >= 0; --i) ans[i] = Math.max(ans[i], ans[i + 1]); return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution: # Similar to 1950. Maximum of Minimum Values in All Subarrays def findMaximums(self, nums: List[int]) -> List[int]: n = len(nums) ans = [0] * n # prevMin[i] := index k s.t. nums[k] is the prev min in nums[:i] prevMin = [-1] * n # nextMin[i] := index k s.t. nums[k] is the next min in nums[i + 1:] nextMin = [n] * n stack = [] for i, num in enumerate(nums): while stack and nums[stack[-1]] > nums[i]: index = stack.pop() nextMin[index] = i if stack: prevMin[i] = stack[-1] stack.append(i) # For each nums[i], let l = nextMin[i] + 1 and r = nextMin[i] - 1. # nums[i] is the minimun in nums[l..r]. # So, the ans[r - l + 1] will be at least nums[i]. for num, l, r in zip(nums, prevMin, nextMin): sz = r - l - 1 ans[sz - 1] = max(ans[sz - 1], num) # ans[i] should always >= ans[i + 1:]. for i in range(n - 2, -1, -1): ans[i] = max(ans[i], ans[i + 1]) return ans