Leetcode 6207 -- dp/思维/双指针

题目描述

max min

思路

思维代码

class Solution {
    func countSubarrays(_ nums: [Int], _ minK: Int, _ maxK: Int) -> Int {
        let segments = nums.split { $0 > maxK || $0 < minK}
        var ans = 0
        for s in segments {
            let seg = [Int](s)
            guard seg.contains(minK) && seg.contains(maxK) else {continue}
            let N = seg.count
            var latestMinKIdx = -1
            var latestMaxKIdx = -1

            for i in 0..<N {
                if seg[i] == minK {
                    latestMinKIdx = i
                }
                if seg[i] == maxK {
                    latestMaxKIdx = i
                }
                let necessaryIdx = min(latestMinKIdx, latestMaxKIdx)
                if necessaryIdx != -1 {
                    ans += necessaryIdx + 1
                }
            }
        }
        return ans
    }
}

class Solution {
    func countSubarrays(_ nums: [Int], _ minK: Int, _ maxK: Int) -> Int {
        var ans = 0
        var left = -1
        var latestMinKIdx = -1
        var latestMaxKIdx = -1
        let N = nums.count
        for i in 0..<N {
            if nums[i] == minK {
                latestMinKIdx = i
            }
            if nums[i] == maxK {
                latestMaxKIdx = i
            }
            if nums[i] >= minK && nums[i] <= maxK {
                let necessaryIdx = min(latestMinKIdx, latestMaxKIdx)
                if necessaryIdx != -1 {
                    ans += necessaryIdx - left
                }
            } else {
                latestMaxKIdx = -1
                latestMinKIdx = -1
                left = i
            }
        }
        return ans
    }
}

作者：RobinLiu
链接：https://leetcode.cn/problems/count-subarrays-with-fixed-bounds/solution/by-robinliu-0x9r/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

dp代码

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int minx, int maxn) {
        /*
        以条件A表示最大值为maxn，条件B表示最小值为minx，设置dp[nums.length][4]数组
        dp[i][0/1/2/3]分别表示分别满足下面条件的子数组的个数:
            [0]: 以nums[i]为结尾的子数组中满足条件A&&B的, maxn, minx
            [1]: 只满足条件A的, maxn
            [2]: 只满足条件B的, minx
            [3]: 两个条件都不满足但没有超出[minx,maxn]范围的, null
        再一次遍历每次根据nums[i]和dp[i-1]确定dp[i]
        */
        int n = nums.size();
        long long res = 0;
        vector<vector<long long>> dp(n, vector<long long>(4));
        // 由于 nums[0] 前面没有元素无法dp，所以预处理nums[0]
        if(nums[0] == maxn && nums[0] == minx)  dp[0][0] = 1;
        else if(nums[0] == maxn)    dp[0][1] = 1;
        else if(nums[0] == minx)    dp[0][2] = 1;
        else if(nums[0] >= minx && nums[0] <= maxn) dp[0][3] = 1;
        res += dp[0][0];
        
        for(int i = 1; i < n; i ++ )
        {
            if(nums[i] == maxn && nums[i] == minx)  
            {
                dp[i][0] = 1 + dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3];
            }
            else if(nums[i] == maxn)   
            {
                dp[i][1] = 1 + dp[i - 1][1] + dp[i - 1][3];
                dp[i][0] = dp[i - 1][2] + dp[i - 1][0];
            }
            else if(nums[i] == minx)
            {
                dp[i][2] = 1 + dp[i - 1][2] + dp[i - 1][3];
                dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
            }
            else if(nums[i] >= minx && nums[i] <= maxn)
            {
                dp[i][0] = dp[i - 1][0];
                dp[i][1] = dp[i - 1][1];
                dp[i][2] = dp[i - 1][2];
                dp[i][3] = 1 + dp[i - 1][3];
            }
            res += dp[i][0];
        }
        return res;
    }
};

借鉴

思维

dp，太牛了

codeforce