[Swift]LeetCode795. 区间子数组个数 | Number of Subarrays with Bounded Maximum

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10547191.html 
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

We are given an array A of positive integers, and two positive integers L and R (L <= R).

Return the number of (contiguous, non-empty) subarrays such that the value of the maximum array element in that subarray is at least L and at most R.

Example :
Input: 
A = [2, 1, 4, 3]
L = 2
R = 3
Output: 3
Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].

Note:

• L, R  and A[i] will be an integer in the range [0, 10^9].
• The length of A will be in the range of [1, 50000].

---

给定一个元素都是正整数的数组A ，正整数 L 以及 R (L <= R)。

求连续、非空且其中最大元素满足大于等于L 小于等于R的子数组个数。

例如 :
输入: 
A = [2, 1, 4, 3]
L = 2
R = 3
输出: 3
解释: 满足条件的子数组: [2], [2, 1], [3].

注意:

• L, R  和 A[i] 都是整数，范围在 [0, 10^9]。
• 数组 A 的长度范围在[1, 50000]。

---

Runtime: 256ms

Memory Usage: 19.6 MB

class Solution {
    func numSubarrayBoundedMax(_ A: [Int], _ L: Int, _ R: Int) -> Int {
        var res:Int = 0
        var left:Int = -1
        var right:Int = -1
        for i in 0..<A.count
        {
            if A[i] > R
            {
                left = i
                right = i
                continue
            }
            if A[i] >= L
            {
                right = i
            }
            res += right - left
        }
        return res
    }
}

---

Runtime: 288 ms

Memory Usage: 19.6 MB

class Solution {
    func numSubarrayBoundedMax(_ A: [Int], _ L: Int, _ R: Int) -> Int {
         var first = 0,second = 0
        var result = 0,rangeCount = 0
        
        while second < A.count && first < A.count {
            if A[second] >= L && A[second] <= R {
                result += (second - first + 1)
                rangeCount = second - first + 1
            } else if (A[second] < L) {
                result += rangeCount
            } else { // A[second] > R
                first = second + 1
                rangeCount = 0
            }
            second += 1
        }
        return result
    }    
}

---

300ms

class Solution {
    func numSubarrayBoundedMax(_ A: [Int], _ L: Int, _ R: Int) -> Int {
        var result = 0
        var numberOfLows = 0
        var numberOfEquals = 0
        enum Status {
            case equal
            case low
            case high
        }
        var status = Status.equal
        
        for (_, value) in A.enumerated() {
            switch status {
            case .equal:
                if value < L {
                    numberOfLows = 1
                    numberOfEquals += 1
                } else if value > R {
                    result += numberOfSubarrayInLength(numberOfEquals)
                    numberOfEquals = 0
                } else {
                    numberOfEquals += 1
                }
            case .low:
                if value < L {
                    numberOfLows += 1
                    numberOfEquals += 1
                } else if value > R {
                    result += numberOfSubarrayInLength(numberOfEquals)
                    numberOfEquals = 0
                    result -= numberOfSubarrayInLength(numberOfLows)
                    numberOfLows = 0
                } else {
                    numberOfEquals += 1
                    result -= numberOfSubarrayInLength(numberOfLows)
                    numberOfLows = 0
                }
            case .high:
                if value < L {
                    numberOfLows = 1
                    numberOfEquals = 1
                } else if value > R {
                    
                } else {
                    numberOfLows = 0
                    numberOfEquals = 1
                }
            }
            if value < L {
                status = .low
            } else if value > R {
                status = .high
            } else {
                status = .equal
            }
        }
        result -= numberOfSubarrayInLength(numberOfLows)
        result += numberOfSubarrayInLength(numberOfEquals)
        return result
    }
    
    func numberOfSubarrayInLength(_ n: Int) -> Int {
        if n <= 0 {
            return 0
        }
        
        return n * (n + 1) / 2
    }
}

---

356ms

class Solution {
    func numSubarrayBoundedMax(_ A: [Int], _ L: Int, _ R: Int) -> Int {
        var count = 0
        for i in 0..<A.count {
            var currMax = A[i]
            for j in i..<A.count {
                currMax = max(currMax, A[j])
                if currMax >= L && currMax <= R {
                    count += 1
                } else if currMax > R {
                    break
                }
            }
        }
        return count
    }
}

---

3816ms

class Solution {
    func numSubarrayBoundedMax(_ A: [Int], _ L: Int, _ R: Int) -> Int {
        if A.count <= 0 { return 0 }
        var cursor = 0
        var count = 0
        while cursor < A.count {
            for i in cursor ..< A.count {
                let temp = A[cursor...i]
                let max = temp.max()!
                if max > R {
                    break
                }
                if max >= L {
                    count += 1
                }
            }
            cursor += 1
        }
        return count
    }
}