[Java/투포인터] 리트코드 2962. Count Subarrays Where Max Element Appears at Least K Times

🤔 Intuition

특정 element의 개수를 세가면서 부분수열의 개수를 구하는 문제이므로 투포인터 문제임을 알 수 있다.

🔎 Algorithm & Complexity

* @algorithm two pointer
* @time O(N) : 10ms
* @memory O(N) : 61.12 MB

👨🏻‍💻 Logic

중요 포인트는, right를 증가시키다가, max element가 k번 등장하는 경우에 "nums의 총 길이 - right의 index"를 연산하여 "max element가 k번 보다 더 많이 등장하는 경우의 수"를 단 한번의 연산으로 구해내는 작업이었다. 이를 통해 추가적인 포인터 이동 연산 없이 O(N)으로 문제를 해결할 수 있었다.

public class LeetCode_2962 { // Count Subarrays Where Max Element Appears at Least K Times
    /**
     * @param nums given number arrray
     * @param k the number of times at least the max element appears on each subarray
     * @return the number of subarrays where the maximum element of nums appears at least k times in that subarray
     */
    public long countSubarrays(int[] nums, int k) {
        int maxVal = Arrays.stream(nums).max().getAsInt();

        int left = 0;
        int right = 0;
        int count = 0;
        long ans = 0;
        while (right < nums.length || left > right) {
            if (nums[right] == maxVal) {
                count++;
            }
            while (count >= k) {
                ans += nums.length - right;
                if (nums[left] == maxVal) {
                    count--;
                }
                left++;
            }
            right++;
        }
        return ans;
    }
}