LeetCode 2444. Count Subarrays With Fixed Bounds

原题链接在这里：https://leetcode.com/problems/count-subarrays-with-fixed-bounds/

题目：

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

题解：

For valid subarray, it must have both minK and maxK.

When iterate nums[i], it is out of [minK, maxK], we need to set the start of subarray as i + 1.

When we see minK and maxK, update last seen index for minK and maxK.

The start of subarray could be choosen from j to min(lastMinInd, lastMaxInd). 

e.g. [1, 3, 5, 1, 7, 5]. minK = 1, maxK = 5.

When ind = 3, num = 1. start of subarray could be 1, 3, 5. The corresponding subarray is [1, 3, 5, 1], [3, 5, 1] and [5, 1].

Time Complexity: O(n). n = nums.length.

Space: O(1).

AC Java:

 1 class Solution {
 2     public long countSubarrays(int[] nums, int minK, int maxK) {
 3         int n = nums.length;
 4         int startInd = 0;
 5         int lastMinInd = -1;
 6         int lastMaxInd = -1;
 7         long res = 0;
 8         for(int i = 0; i < n; i++){
 9             if(nums[i] < minK || nums[i] > maxK){
10                 lastMinInd = lastMaxInd = -1;
11                 startInd = i + 1;
12             }
13             
14             if(nums[i] == minK){
15                 lastMinInd = i;
16             }
17             
18             if(nums[i] == maxK){
19                 lastMaxInd = i;
20             }
21             
22             res += Math.max(0L, Math.min(lastMinInd, lastMaxInd) - startInd + 1);
23         }
24         
25         return res;
26     }
27 }

类似Number of Subarrays with Bounded Maximum.

原文地址：http://www.cnblogs.com/Dylan-Java-NYC/p/16796157.html