資訊

• Question: 2444. Count Subarrays With Fixed Bounds
• From: Leetcode Daily Challenge 2024.03.31
• Difficulty: Hard

---

目錄

• 資訊
• 目錄
• 題目
• 解法
  • 概念
  • 程式碼
• 複雜度
  • 時間複雜度
  • 空間複雜度
• Congratulations!

---

題目

You are given an integer array nums and two integers minK and maxK.

A fixed-bound subarray of nums is a subarray that satisfies the following conditions:

• The minimum value in the subarray is equal to minK.
• The maximum value in the subarray is equal to maxK.

Return the number of fixed-bound subarrays.

A subarray is a contiguous part of an array.

Example 1:

• Input: nums = [1,3,5,2,7,5], minK = 1, maxK = 5
• Output: 2
• Explanation: The fixed-bound subarrays are [1,3,5] and [1,3,5,2].

Example 2:

• Input: nums = [1,1,1,1], minK = 1, maxK = 1
• Output: 10
• Explanation: Every subarray of nums is a fixed-bound subarray. There are 10 possible subarrays.

Constraints:

• 2 <= nums.length <= 105
• 1 <= nums[i], minK, maxK <= 106

---

解法

概念

難了這次，昨天還說自己是 sliding window 大師，結果今天直接撞牆，看到題目還以為多一個 pointer 可以解出來，不過看起來是有一些東西沒考慮到，sliding window week 應該結束了，下次再碰到這邊的題目要來思考怎麼樣可以生出好且完整的測資！

這次就是看 solution 解出來的，還滿酷的想法，畢竟我為了想這個做法列了一張表一一對應去看所有情況，發現他說的是真的！Divide and Conquer 果真很重要！

來說膝下這題的解法：首先會需要三個 pointer，分別指到最新的 minK index、maxK index、還有超出範圍的 bad 的 index，這三個 index 一開始都指到 -1，代表還沒遇到，而設成 -1 對於解答不受影響，可以看下面表格對應說明。

接著會迭代走訪 nums 裡面每一個 element，只要遇到 minK、maxK、或是 bad 就會更改 pointer 的值，至於 ans 怎麼新增，會以 min(minIndex,maxIndex) - bad 的值判斷，如果大於 0 就代表有心區間可以新增，那就把算出來的區間數加上去，否則代表沒有區間可以新增，就會是 +0，當然我沒把 +0 寫出來就是了 : )，這部分詳細可以看表格，表格有把所有情況寫出來

Situation	min Index	max Index	bad	Result	計算過程	ans 往上加
目前只遇到 (minK, maxK) 區間內的數字	-1	-1	-1	沒有東西可以加	(-1)-(-1)	0
遇到 minK 而已	V	-1	-1	沒有東西可以加	(-1)-(-1)	0
遇到 minK 而已	-1	V	-1	沒有東西可以加	(-1)-(-1)	0
遇到超出範圍的	-1	-1	V	沒有東西可以加	(-1)-(-1)	0
合法 interval 從頭開始有包含這段的都可以	大	小	-1	[(0:小):(大:i)]	小+1	小+1
合法 interval 從頭開始有包含這段的都可以	小	大	-1	[(0:小):(大:i)]	小+1	小+1
不合法 interval 少了 maxK	大	-1	小	沒有東西可以加	-1-小	0
不合法 interval 少了 maxK	小	-1	大	沒有東西可以加	-1-小	0
不合法 interval 少了 minK	-1	大	大	沒有東西可以加	-1-小	0
不合法 interval 少了 minK	-1	小	小	沒有東西可以加	-1-小	0
合法 interval 從 bad 之後開始有包含這段都行	大	中	小	[(小:中):(大:i)]	中-小	中-小
不合法 interval bad 是程咬金	大	小	中	沒有東西可以加	小-中	0
合法 interval 從 bad 之後開始有包含這段都行	中	大	小	[(小:中):(大:i)]	中-小	中-小
不合法 interval bad 是程咬金	中	小	大	沒有東西可以加	小-大	0
不合法 interval bad 是程咬金	小	大	中	沒有東西可以加	小-中	0
不合法 interval bad 是程咬金	小	中	大	沒有東西可以加	小-大	0

這邊最後有一個要回答的問題，會不會有重新計算的區間？因為新的一輪如果 interval 都沒有改變，不就代表會重新計算？這個答案當然是 No，因為上面柿子的計算只有在計算個數，當 pointer 沒有改變，代表該輪數字出現在 (minkK,maxK) 區間內，等於這輪計算的是到該輪數字的 subarray，並沒有多算！

程式碼

class Solution:
    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
        ans = 0
        minIndex = -1
        maxIndex = -1
        bad = -1
        for i in range(len(nums)):
            if nums[i] == minK:
                minIndex = i
            if nums[i] == maxK:
                maxIndex = i
            if nums[i] < minK or nums[i] > maxK:
                bad = i
            
            tmp = min( minIndex, maxIndex ) - bad
            if tmp > 0:
                ans += tmp
        return ans

---

複雜度

時間複雜度

就是走過 nums，所以是

$O(n)$

空間複雜度

空間其實也指又記錄這三個 pointer 和一點點其他 variable，所以是

$O(1)$

Congratulations!

拿到三月的 streak badge 了！