2962. Count Subarrays Where Max Element Appears at Least K Times - Medium

前往題目

想法

• 先找出最大值
• Sliding window

思路

1. 先找到最大值
2. 以右指針疊代整個陣列
3. 遇到最大值，計數+1
4. 與左指針維持合法的window，不合法就要移動左指針直到合法
5. 當window的最大值有k個，紀錄有幾個subarray

這題在最後卡很久，原來是要用long回傳

Code

class Solution {
    public long countSubarrays(int[] nums, int k) {
        int maxElement = Integer.MIN_VALUE;
        int maxElementCount = 0;
        int l = 0;
        long res = 0L;

        // Find max element
        maxElement = Arrays.stream(nums).max().getAsInt();

        for (int r = 0; r < nums.length; ++r) {
            // Increase count if encounters max element
            if (nums[r] == maxElement) {
                maxElementCount += 1;
            }

            // Shrink the window to maintain the valid window
            while (maxElementCount > k || (l <= r && maxElementCount == k && nums[l] != maxElement)) {
                // Left pointer is pointing a maxElement
                if (nums[l] == maxElement) {
                    --maxElementCount;
                }
                l += 1; // Move left pointer
            }

            // Valid window
            if (maxElementCount == k) {
                res += l + 1;
            }
        }

        return res; 
    }
}