MediumRating 1817

795. Number of Subarrays with Bounded Maximum

arraytwo-pointersprefix-sum

在 LeetCode 上作答 ↗

解題說明

題目描述

給定整數陣列 nums 和兩個整數 left、right（left <= right），回傳最大元素介於 [left, right] 之間的子陣列個數（子陣列必須連續）。

範例：nums = [2, 1, 4, 3], left = 2, right = 3

[2] → max=2 ✓
[2,1] → max=2 ✓
[1] → max=1 ✗（< left）
[4] → max=4 ✗（> right）
[4,3] → max=4 ✗
[3] → max=3 ✓
[2,1,4] → max=4 ✗
[1,4] → max=4 ✗
[1,4,3] → max=4 ✗
[2,1,4,3] → max=4 ✗ → 答案：3

解題思路

思路一：計數函式 count(bound) + 差分

定義輔助函式 count(bound)：計算最大元素 ≤ bound 的子陣列個數。

答案即為：count(right) - count(left - 1)

count(right) 計算最大值 ≤ right 的子陣列數（包含最大值恰好在 [left, right] 和最大值 < left 兩類）
count(left - 1) 計算最大值 < left 的子陣列數
相減得到最大值恰在 [left, right] 的子陣列數

count(bound) 的實作：維護當前連續「最大值 ≤ bound」的子陣列起始點。遇到 nums[i] > bound 時重置計數；否則當前以 i 結尾的合法子陣列有 i - start + 1 個（start 為上次重置點的下一位置）。

思路二：一次掃描三種情況

遍歷陣列，對每個元素判斷其值所屬範圍：

值 > right：重置左邊界 left_bound = i，以此元素結尾的子陣列無效。
值在 [left, right]：更新 prev = i（最後一個值在範圍內的索引）；以 i 結尾的有效子陣列數為 i - left_bound。
值 < left：有效子陣列數為 prev - left_bound（沿用上次在範圍內的元素決定的數量）。

兩種思路都是 O(n) 時間，思路一更容易推廣，思路二更節省程式碼行數。

C++ 解法

複雜度分析

時間複雜度

O(n)，其中 n 為陣列長度。

方案一：count 函式被呼叫兩次，每次線性遍歷，共 O(2n) = O(n)。
方案二：只需一次遍歷，O(n)。

空間複雜度

O(1)，只使用了常數個額外變數，不需要額外陣列。

虛擬碼

Approach 1:
count(nums, bound):
1. result = 0, cur = 0
2. For each x in nums:
   a. If x <= bound: cur += 1
   b. Else: cur = 0
   c. result += cur
3. Return result

numSubarrayBoundedMax(nums, left, right):
1. Return count(nums, right) - count(nums, left - 1)

Approach 2 (single pass):
1. leftBound = -1, prev = -1, result = 0
2. For i from 0 to n-1:
   a. If nums[i] > right: leftBound = i
   b. If nums[i] >= left: prev = i
   c. result += prev - leftBound
3. Return result

其他解法

替代方案

方案一：暴力枚舉

雙重迴圈枚舉所有子陣列 [i, j]，用第三層迴圈（或維護滾動最大值）計算子陣列最大元素，判斷是否在 [left, right] 內。

優點：邏輯最直觀，無需推導。
缺點：時間 O(n²) 甚至 O(n³)（不維護滾動最大值），n=10^5 時無法接受。

方案二：單調棧

利用單調棧追蹤每個元素作為子陣列最大值的範圍（左右邊界），然後統計每個元素作為最大值、且值在 [left, right] 內的子陣列數。

優點：時間 O(n)，空間 O(n)；對「每個元素作為最大值/最小值的貢獻」型問題是通用框架。
缺點：實作比 count(right) - count(left-1) 更複雜；需要正確處理重複元素的邊界（嚴格 vs 非嚴格）。

方案三：前綴計數陣列（不實際可行）

預先統計以每個位置結尾的、最大值在各範圍的子陣列數，建立前綴計數表。

缺點：需要二維前綴統計，空間和時間均為 O(n × max_val)，完全不可行。

延伸思考

延伸問題

子陣列最小值在 [left, right] 之間：與本題類似，只需把「最大值」換成「最小值」，同樣可以用 count(right) - count(left-1) 的框架，其中 count(bound) 統計最小值 ≤ bound 的子陣列數（改為遇到 nums[i] > bound 時繼續計數，遇到 nums[i] <= bound 時記錄）。
最大值等於 target 的子陣列數：若要求最大值恰好等於某個值 target，即 count(target) - count(target - 1)，是本題 left = right = target 的特例。
推廣：最大值與最小值都在範圍內：若要求子陣列的最大值在 [maxL, maxR] 且最小值在 [minL, minR] 之間，問題複雜度顯著增加，需要同時追蹤最大值和最小值的有效段，可結合兩個指標或使用單調雙端佇列（monotonic deque）。