2334. Subarray With Elements Greater Than Varying Threshold

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

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;
    }
};

• T: $O(n)$
• S: $O(n)$

另外一種寫法

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;
    }
};

• T: $O(n)$
• S: $O(n)$