Hard

题目描述

给你一个整数数组 nums 和一个整数 threshold。

找到 nums 的任一长度为 k 的子数组，使得该子数组中每个元素都大于 threshold / k。

返回任一这样的子数组的大小。如果不存在这样的子数组，返回 -1。

子数组是数组中一个连续的非空元素序列。

示例 1：

输入：nums = [1,3,4,3,1], threshold = 6
输出：3
解释：子数组 [3,4,3] 的大小为 3，每个元素都大于 6 / 3 = 2。
注意这是唯一有效的子数组。

示例 2：

输入：nums = [6,5,6,5,8], threshold = 7
输出：1
解释：子数组 [8] 的大小为 1，8 > 7 / 1 = 7。所以返回 1。
注意子数组 [6,5] 的大小为 2，每个元素都大于 7 / 2 = 3.5。
类似地，子数组 [6,5,6], [6,5,6,5], [6,5,6,5,8] 也满足给定条件。
因此，也可以返回 2, 3, 4, 或 5。

约束条件：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i], threshold <= 10^9

解题思路

解题思路

这道题的关键观察是：对于一个满足条件的子数组，其中的最小元素必须大于 threshold / length。换句话说，如果我们固定一个元素作为子数组的最小值，那么包含这个元素的最大子数组长度是确定的。

核心思路：

  1. 对于数组中的每个元素 nums[i]，找到以它为最小值的最大子数组
  2. 检查在这个子数组中，nums[i] 是否大于 threshold / length
  3. 如果满足条件，返回子数组长度

实现方法：

使用单调栈找到每个元素的左右边界：

  • 找到每个元素左侧第一个小于它的元素位置
  • 找到每个元素右侧第一个小于等于它的元素位置
  • 这样就能确定以当前元素为最小值的最大子数组范围

算法步骤：

  1. 使用单调递增栈，分别计算每个元素的左右边界
  2. 对于每个元素，计算以它为最小值的最大子数组长度
  3. 检查是否满足 nums[i] > threshold / length 的条件
  4. 返回第一个满足条件的长度

这种方法的时间复杂度为 O(n)，空间复杂度为 O(n)，是最优解法。

代码实现

class Solution {
public:
    int validSubarraySize(vector<int>& nums, int threshold) {
        int n = nums.size();
        vector<int> left(n, -1), right(n, n);
        stack<int> st;
        
        // 找到每个元素左侧第一个小于它的元素
        for (int i = 0; i < n; i++) {
            while (!st.empty() && nums[st.top()] >= nums[i]) {
                st.pop();
            }
            if (!st.empty()) {
                left[i] = st.top();
            }
            st.push(i);
        }
        
        // 清空栈
        while (!st.empty()) st.pop();
        
        // 找到每个元素右侧第一个小于等于它的元素
        for (int i = n - 1; i >= 0; i--) {
            while (!st.empty() && nums[st.top()] > nums[i]) {
                st.pop();
            }
            if (!st.empty()) {
                right[i] = st.top();
            }
            st.push(i);
        }
        
        // 检查每个元素作为最小值的子数组
        for (int i = 0; i < n; i++) {
            int len = right[i] - left[i] - 1;
            if (nums[i] > threshold / (double)len) {
                return len;
            }
        }
        
        return -1;
    }
};

class Solution:
    def validSubarraySize(self, nums: List[int], threshold: int) -> int:
        n = len(nums)
        left = [-1] * n
        right = [n] * n
        stack = []
        
        # 找到每个元素左侧第一个小于它的元素
        for i in range(n):
            while stack and nums[stack[-1]] >= nums[i]:
                stack.pop()
            if stack:
                left[i] = stack[-1]
            stack.append(i)
        
        # 清空栈
        stack.clear()
        
        # 找到每个元素右侧第一个小于等于它的元素
        for i in range(n - 1, -1, -1):
            while stack and nums[stack[-1]] > nums[i]:
                stack.pop()
            if stack:
                right[i] = stack[-1]
            stack.append(i)
        
        # 检查每个元素作为最小值的子数组
        for i in range(n):
            length = right[i] - left[i] - 1
            if nums[i] > threshold / length:
                return length
        
        return -1

public class Solution {
    public int ValidSubarraySize(int[] nums, int threshold) {
        int n = nums.Length;
        int[] left = new int[n];
        int[] right = new int[n];
        Stack<int> stack = new Stack<int>();
        
        // 初始化边界
        for (int i = 0; i < n; i++) {
            left[i] = -1;
            right[i] = n;
        }
        
        // 找到每个元素左侧第一个小于它的元素
        for (int i = 0; i < n; i++) {
            while (stack.Count > 0 && nums[stack.Peek()] >= nums[i]) {
                stack.Pop();
            }
            if (stack.Count > 0) {
                left[i] = stack.Peek();
            }
            stack.Push(i);
        }
        
        // 清空栈
        stack.Clear();
        
        // 找到每个元素右侧第一个小于等于它的元素
        for (int i = n - 1; i >= 0; i--) {
            while (stack.Count > 0 && nums[stack.Peek()] > nums[i]) {
                stack.Pop();
            }
            if (stack.Count > 0) {
                right[i] = stack.Peek();
            }
            stack.Push(i);
        }
        
        // 检查每个元素作为最小值的子数组
        for (int i = 0; i < n; i++) {
            int length = right[i] - left[i] - 1;
            if (nums[i] > (double)threshold / length) {
                return length;
            }
        }
        
        return -1;
    }
}

var validSubarraySize = function(nums, threshold) {
    const n = nums.length;
    const left = new Array(n).fill(-1);
    const right = new Array(n).fill(n);
    const stack = [];
    
    // 找到每个元素左侧第一个小于它的元素
    for (let i = 0; i < n; i++) {
        while (stack.length > 0 && nums[stack[stack.length - 1]] >= nums[i]) {
            stack.pop();
        }
        if (stack.length > 0) {
            left[i] = stack[stack.length - 1];
        }
        stack.push(i);
    }
    
    // 清空栈
    stack.length = 0;
    
    // 找到每个元素右侧第一个小于等于它的元素
    for (let i = n - 1; i >= 0; i--) {
        while (stack.length > 0 && nums[stack[stack.length - 1]] > nums[i]) {
            stack.pop();
        }
        if (stack.length > 0) {
            right[i] = stack[stack.length - 1];
        }
        stack.push(i);
    }
    
    // 检查每个元素作为最小值的子数组
    for (let i = 0; i < n; i++) {
        const length = right[i] - left[i] - 1;
        if (nums[i] > threshold / length) {
            return length;
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)每个元素最多入栈出栈一次，总共遍历数组3次
空间复杂度O(n)需要额外的数组存储左右边界和单调栈

相关题目