Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1950.html

1950. Maximum of Minimum Values in All Subarrays

Level

Medium

Description

You are given an integer array nums of size n. You are asked to solve n queries for each integer i in the range 0 <= i < n.

To solve the i-th query:

  1. Find the minimum value in each possible subarray of size i + 1 of the array nums.
  2. Find the maximum of those minimum values. This maximum is the answer to the query.

Return a 0-indexed integer array ans of size n such that ans[i] is the answer to the i-th query.

A subarray is a contiguous sequence of elements in an array.

Example 1:

Input: nums = [0,1,2,4]

Output: [4,2,1,0]

Explanation: i=0:

  • The subarrays of size 1 are [0], [1], [2], [4]. The minimum values are 0, 1, 2, 4.
  • The maximum of the minimum values is 4.

i=1:

  • The subarrays of size 2 are [0,1], [1,2], [2,4]. The minimum values are 0, 1, 2.
  • The maximum of the minimum values is 2.

i=2:

  • The subarrays of size 3 are [0,1,2], [1,2,4]. The minimum values are 0, 1.
  • The maximum of the minimum values is 1.

i=3:

  • There is one subarray of size 4, which is [0,1,2,4]. The minimum value is 0.
  • There is only one value, so the maximum is 0.

Example 2:

Input: nums = [10,20,50,10]

Output: [50,20,10,10]

Explanation: i=0:

  • The subarrays of size 1 are [10], [20], [50], [10]. The minimum values are 10, 20, 50, 10.
  • The maximum of the minimum values is 50.

i=1:

  • The subarrays of size 2 are [10,20], [20,50], [50,10]. The minimum values are 10, 20, 10.
  • The maximum of the minimum values is 20.

i=2:

  • The subarrays of size 3 are [10,20,50], [20,50,10]. The minimum values are 10, 10.
  • The maximum of the minimum values is 10.

i=3:

  • There is one subarray of size 4, which is [10,20,50,10]. The minimum value is 10.
  • There is only one value, so the maximum is 10.

Constraints:

  • n == nums.length
  • 1 <= n <= 10^5
  • 0 <= nums[i] <= 10^9

Solution

Use monotonic stack, where the elements of the corresponding indices are ascending from bottom to top of the stack. Use two arrays left and right to store each element’s closest left index and right index such that the elements at the indices are less than the current element. Loop over nums from left to right, and fill in the arrays left and right.

Then loop over 0 <= i < n. For each i, let num = nums[i], and the range length with num as the smallest element is range = right[i] - left[i] - 1. Let ans[range - 1] be the maximum of such values of num. Then for i from n - 2 to 0, ans[i] is the maximum of ans[i] and ans[i + 1]. Finally, return ans.

  • class Solution {
    public int[] findMaximums(int[] nums) {
        int length = nums.length;
        int[] left = new int[length];
        int[] right = new int[length];
        Arrays.fill(right, length);
        int minimum = Integer.MAX_VALUE;
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < length; i++) {
            minimum = Math.min(minimum, nums[i]);
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i])
                right[stack.pop()] = i;
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        int[] maximums = new int[length];
        Arrays.fill(maximums, minimum);
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            int range = right[i] - left[i] - 1;
            maximums[range - 1] = Math.max(maximums[range - 1], num);
        }
        for (int i = length - 2; i >= 0; i--)
            maximums[i] = Math.max(maximums[i], maximums[i + 1]);
        return maximums;
    }
}

############

class Solution {
    public int[] findMaximums(int[] nums) {
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(left, -1);
        Arrays.fill(right, n);
        Deque<Integer> stk = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) {
            while (!stk.isEmpty() && nums[stk.peek()] >= nums[i]) {
                stk.pop();
            }
            if (!stk.isEmpty()) {
                left[i] = stk.peek();
            }
            stk.push(i);
        }
        stk.clear();
        for (int i = n - 1; i >= 0; --i) {
            while (!stk.isEmpty() && nums[stk.peek()] >= nums[i]) {
                stk.pop();
            }
            if (!stk.isEmpty()) {
                right[i] = stk.peek();
            }
            stk.push(i);
        }
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            int m = right[i] - left[i] - 1;
            ans[m - 1] = Math.max(ans[m - 1], nums[i]);
        }
        for (int i = n - 2; i >= 0; --i) {
            ans[i] = Math.max(ans[i], ans[i + 1]);
        }
        return ans;
    }
}

  • class Solution {
public:
    vector<int> findMaximums(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n, -1);
        vector<int> right(n, n);
        stack<int> stk;
        for (int i = 0; i < n; ++i) {
            while (!stk.empty() && nums[stk.top()] >= nums[i]) {
                stk.pop();
            }
            if (!stk.empty()) {
                left[i] = stk.top();
            }
            stk.push(i);
        }
        stk = stack<int>();
        for (int i = n - 1; i >= 0; --i) {
            while (!stk.empty() && nums[stk.top()] >= nums[i]) {
                stk.pop();
            }
            if (!stk.empty()) {
                right[i] = stk.top();
            }
            stk.push(i);
        }
        vector<int> ans(n);
        for (int i = 0; i < n; ++i) {
            int m = right[i] - left[i] - 1;
            ans[m - 1] = max(ans[m - 1], nums[i]);
        }
        for (int i = n - 2; i >= 0; --i) {
            ans[i] = max(ans[i], ans[i + 1]);
        }
        return ans;
    }
};


  • class Solution:
    def findMaximums(self, nums: List[int]) -> List[int]:
        n = len(nums)
        left = [-1] * n
        right = [n] * n
        stk = []
        for i, x in enumerate(nums):
            while stk and nums[stk[-1]] >= x:
                stk.pop()
            if stk:
                left[i] = stk[-1]
            stk.append(i)
        stk = []
        for i in range(n - 1, -1, -1):
            while stk and nums[stk[-1]] >= nums[i]:
                stk.pop()
            if stk:
                right[i] = stk[-1]
            stk.append(i)
        ans = [0] * n
        for i in range(n):
            m = right[i] - left[i] - 1
            ans[m - 1] = max(ans[m - 1], nums[i])
        for i in range(n - 2, -1, -1):
            ans[i] = max(ans[i], ans[i + 1])
        return ans


  • func findMaximums(nums []int) []int {
	n := len(nums)
	left := make([]int, n)
	right := make([]int, n)
	for i := range left {
		left[i], right[i] = -1, n
	}
	stk := []int{}
	for i, x := range nums {
		for len(stk) > 0 && nums[stk[len(stk)-1]] >= x {
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			left[i] = stk[len(stk)-1]
		}
		stk = append(stk, i)
	}
	stk = []int{}
	for i := n - 1; i >= 0; i-- {
		x := nums[i]
		for len(stk) > 0 && nums[stk[len(stk)-1]] >= x {
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			right[i] = stk[len(stk)-1]
		}
		stk = append(stk, i)
	}
	ans := make([]int, n)
	for i := range ans {
		m := right[i] - left[i] - 1
		ans[m-1] = max(ans[m-1], nums[i])
	}
	for i := n - 2; i >= 0; i-- {
		ans[i] = max(ans[i], ans[i+1])
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

All Problems

All Solutions