# 資訊

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

---

# 目錄

:::info
[TOC]
:::

---

# 題目

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:
:::success
* 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:
:::success
* 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:
:::success
* 2 <= `nums.length` <= 105
* 1 <= `nums[i]`, `minK`, `maxK` <= 106
:::

---

# 解法

## 概念

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

這次就是看 [solution](https://leetcode.com/problems/count-subarrays-with-fixed-bounds/solutions/3256543/awesome-logic-beginner-friendy-code-in-python) 解出來的，還滿酷的想法，畢竟我為了想這個做法列了一張表一一對應去看所有情況，發現他說的是真的！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<br>Index | max<br>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<br>從頭開始有包含這段的都可以 | 大 | 小 | -1 | `[(0:小):(大:i)]` | 小+1 | 小+1 |
| 合法 interval<br>從頭開始有包含這段的都可以 | 小 | 大 | -1 | `[(0:小):(大:i)`] | 小+1 | 小+1 |
| 不合法 interval<br>少了 `maxK` | 大 | -1 | 小 | 沒有東西可以加 | -1-小 | 0 |
| 不合法 interval<br>少了 `maxK` | 小 | -1 | 大 | 沒有東西可以加 | -1-小 | 0 |
| 不合法 interval<br>少了 `minK` | -1 | 大 | 大 | 沒有東西可以加 | -1-小 | 0 |
| 不合法 interval<br>少了 `minK` | -1 | 小 | 小 | 沒有東西可以加 | -1-小 | 0 |
| 合法 interval<br>從 bad 之後開始有包含這段都行 | 大 | 中 | 小 | `[(小:中):(大:i)]` | 中-小| 中-小 |
| 不合法 interval<br>`bad` 是程咬金 | 大 | 小 | 中 | 沒有東西可以加 | 小-中 | 0 |
| 合法 interval<br>從 bad 之後開始有包含這段都行 | 中 | 大 | 小 | `[(小:中):(大:i)]` | 中-小 | 中-小 |
| 不合法 interval<br>`bad` 是程咬金 | 中 | 小 | 大 | 沒有東西可以加 | 小-大 | 0 |
| 不合法 interval<br>`bad` 是程咬金 | 小 | 大 | 中 | 沒有東西可以加 | 小-中 | 0 |
| 不合法 interval<br>`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 了！