526互联

[LeetCode] 2334. Subarray With Elements Greater Than Varying Threshold_Hard tag: dp, stack

发布时间 2023-09-29 00:21:35作者: Johnson_强生仔仔

You are given an integer array nums and an integer threshold.

Find any subarray of nums of length k such that every element in the subarray is greater than threshold / k.

Return the size of any such subarray. If there is no such subarray, return -1.

A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

Input: nums = [1,3,4,3,1], threshold = 6
Output: 3
Explanation: The subarray [3,4,3] has a size of 3, and every element is greater than 6 / 3 = 2.
Note that this is the only valid subarray.

Example 2:

Input: nums = [6,5,6,5,8], threshold = 7
Output: 1
Explanation: The subarray [8] has a size of 1, and 8 > 7 / 1 = 7. So 1 is returned.
Note that the subarray [6,5] has a size of 2, and every element is greater than 7 / 2 = 3.5. 
Similarly, the subarrays [6,5,6], [6,5,6,5], [6,5,6,5,8] also satisfy the given conditions.
Therefore, 2, 3, 4, or 5 may also be returned.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i], threshold <= 109

 

1) Brute force T: O(n ^ 3), S: O(1), 三个for loop, 然后判断每一个是否符合条件

2) 最开始以为题目条件是找到符合条件最大的subarray的size，这种情况应该是可以用dynamic programming，类似于利用 [LeetCode] 5. Longest Palindromic Substring _Medium tag: Two pointers的方式，T: O(n ^ 2), S: O(n ^ 2), 牺牲空间来去提升时间, 用dp[i][j] 去记录nums[i:j + 1] 里面mininal的值，每次将mininal的值和target/(j - i + 1) 比较就好。不过题目意思是随便什么subarray的size, 就不需要找到最大的，所以可以考虑用stack

Code

class Solution:
    def validSubarraySize(self, nums: List[int], threshold: int) -> int:
        n = len(nums)
        dp = [[float('inf')] * n for _ in range(n)]
        # initial dp
        for i in range(n):
            dp[i][i] = nums[i]
            if i > 0:
                dp[i - 1][i] = min(nums[i - 1], nums[i])

        for length in range(2, n):
            for start in range(n):
                if start + length < n:
                    dp[start][start + length] = min(dp[start][start + length - 1], nums[start + length])

        for length in range(n - 1, -1, -1):
            for start in range(n):
                if start + length < n and dp[start][start + length] > threshold / (length + 1):
                    return length + 1
        return -1

 

3） T: O(n).  S: O(n)， 用单调非强制性递增stack 就是找到当天num 的左边比它小的index 和右边比它小的index，取中间的然后判断num 是否 > threshold /length.

code

class Solution:
    def validSubarraySize(self, nums: List[int], threshold: int) -> int:
        nums = [0] + nums + [0]
        stack = [0]
        for i in range(1,len(nums)):
            while nums[i] < nums[stack[-1]]:
                cand = nums[stack.pop()]
                length = i - stack[-1] - 1
                if cand > threshold / length:
                    return length
            stack.append(i)
        return -1