HardRating 2381
2334. Subarray With Elements Greater Than Varying Threshold
arraystackunion-findmonotonic-stack
解題說明
Subarray With Elements Greater Than Varying Threshold
題目描述： 給定整數陣列 nums 和整數 threshold，找到一個子陣列，使得子陣列的長度為 k，且子陣列中每個元素都嚴格大於 threshold / k。返回任何一個滿足條件的子陣列大小 k，若不存在則返回 -1。
解題思路： 關鍵觀察：對於每個元素 nums[i]，找到以它為最小值的最大子陣列（使用單調棧找到左右邊界）。如果這個子陣列的長度為 k，且 nums[i] > threshold / k，即 nums[i] * k > threshold，則這就是一個合法答案。
使用單調遞增棧找出每個元素作為最小值的最大範圍 [left[i]+1, right[i]-1]，其中 left[i] 是左邊第一個比 nums[i] 小的元素位置，right[i] 是右邊第一個比 nums[i] 小或等於的元素位置。這樣 k = right[i] - left[i] - 1。
C++ 解法
複雜度分析
時間複雜度：O(n) — 單調棧找左右邊界各 O(n)，最後一次遍歷 O(n)
空間複雜度：O(n) — left、right 陣列及棧
虛擬碼
1. For each element, find left[i] = index of previous smaller element (or -1) 2. For each element, find right[i] = index of next smaller-or-equal element (or n) 3. For each element i: a. k = right[i] - left[i] - 1 (max subarray length where nums[i] is minimum) b. If nums[i] * k > threshold, return k 4. Return -1
其他解法
-
Union-Find（並查集）法：將元素按值從大到小排序，依序加入並合併相鄰的已加入元素。每次合併後檢查連通分量大小 k 是否滿足 min_val * k > threshold。時間複雜度 O(n log n)（排序瓶頸）。
-
二分搜尋 + 滑動窗口最小值：對 k 進行二分搜尋，用單調佇列維護長度為 k 的窗口最小值。時間複雜度 O(n log n)，但不如單調棧方法直接。
延伸思考
- 如果要找出所有滿足條件的 k 值（而非任意一個），如何修改？
- 如果 threshold 是動態變化的（多次查詢不同的 threshold），如何預處理加速？
- 如果條件改為子陣列平均值大於 threshold / k，演算法如何調整？