[LeetCode 2419] Longest Subarray With Maximum Bitwise AND

문제 바로가기

Description

---

You are given an integer array nums of size n.

Consider a non-empty subarray from nums that has the maximum possible bitwise AND.

• In other words, let k be the maximum value of the bitwise AND of any subarray of nums. Then, only subarrays with a bitwise AND equal to k should be considered.

Return the length of the longest such subarray.

The bitwise AND of an array is the bitwise AND of all the numbers in it.

A subarray is a contiguous sequence of elements within an array.

Example 1

---

• Input: nums = [1,2,3,3,2,2]
• Output: 2
• Explanation:
  • The maximum possible bitwise AND of a subarray is 3.
  • The longest subarray with that value is [3,3], so we return 2.

Example 2

---

• Input: nums = [1,2,3,4]
• Output: 1
• Explanation:
  • The maximum possible bitwise AND of a subarray is 4.
  • The longest subarray with that value is [4], so we return 1.

Constraints

---

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6

Hint

---

Hint 1

  Notice that the bitwise AND of two different numbers will always be strictly less than the maximum of those two numbers.
	

Hint 2

  What does that tell us about the nature of the subarray that we should choose?
	

Code

---

내 제출

---

class Solution {
    public int longestSubarray(int[] nums) {
        int mx = Arrays.stream(nums).max().getAsInt();
        int ans = 0, cnt = 0;
        for (int x : nums) {
            if (x == mx) {
                ans = Math.max(ans, ++cnt);
            } else {
                cnt = 0;
            }
        }
        return ans;
    }
}

Runtime	Memory
9 ms	60.9 MB

다른 풀이

---

class Solution {
    public int longestSubarray(int[] nums) {

        int max = nums[0];

        // Find maximum element
        for(int i = 1; i < nums.length; i++) {
            if(nums[i] > max) {
                max = nums[i];
            }
        }

        int count = 0;
        int longest = 0;

        // Count longest continuous streak of max
        for(int i = 0; i < nums.length; i++) {

            if(nums[i] == max) {
                count++;
                longest = Math.max(longest, count);
            } else {
                count = 0;
            }
        }

        return longest;
    }
}

Reference

---

• https://github.com/doocs/leetcode/blob/main/solution/2400-2499/2419.Longest%20Subarray%20With%20Maximum%20Bitwise%20AND/Solution.java