# [2334\. Subarray With Elements Greater Than Varying Threshold](https://leetcode.com/problems/subarray-with-elements-greater-than-varying-threshold/)

- 給予一個數列 `nums`，求一個子數列的大小，使得 `threshold / subarray size` 大於子數列的每個元素。
- 做法類似 84. Largest Rectangle in Histogram 這一題，找遞增的連續柱。

:::spoiler Solution

class Solution {
public:
    int validSubarraySize(vector<int>& nums, int threshold)
    {
        nums.push_back(0);
        int n = nums.size();
        stack<int> stk;
        for (int i = 0; i < n; ++i)
        {
            while (!stk.empty() && nums[stk.top()] > nums[i])
            {
                int h = nums[stk.top()]; stk.pop();
                int w = stk.empty() ? i : i - stk.top() - 1;
                if (h * w > threshold)
                {
                    return w;
                }
            }
            stk.push(i);
        }
        return -1;
    }
};

- 時間複雜度：$O(n)$
- 空間複雜度：$O(n)$
:::

:::spoiler Solution 另外一種寫法

class Solution {
public:
    int validSubarraySize(vector<int>& nums, int threshold)
    {
        nums.push_back(0);
        int n = nums.size();
        stack<int> stk;
        int i = 0;
        while (i < n)
        {
            if (stk.empty() || nums[i] >= nums[stk.top()])
            {
                stk.push(i);
                ++i;
            }
            else
            {
                int h = nums[stk.top()]; stk.pop();
                int w = stk.empty() ? i : i - stk.top() - 1;
                if (h * w > threshold)
                {
                    return w;
                }
            }
        }
        return -1;
    }
};

- 時間複雜度：$O(n)$
- 空間複雜度：$O(n)$
:::