侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

【脑筋急转弯】按位与最大的最长子数组【力扣第 312 场周赛】

GabrielxD
2022-09-26 / 0 评论 / 0 点赞 / 360 阅读 / 563 字
温馨提示:
本文最后更新于 2022-09-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

6189. 按位与最大的最长子数组


给你一个长度为 n 的整数数组 nums

考虑 nums 中进行 **按位与(bitwise AND)**运算得到的值 最大非空 子数组。

  • 换句话说,令 knums 任意 子数组执行按位与运算所能得到的最大值。那么,只需要考虑那些执行一次按位与运算后等于 k 的子数组。

返回满足要求的 最长 子数组的长度。

数组的按位与就是对数组中的所有数字进行按位与运算。

子数组 是数组中的一个连续元素序列。

示例 1:

输入:nums = [1,2,3,3,2,2]
输出:2
解释:
子数组按位与运算的最大值是 3 。
能得到此结果的最长子数组是 [3,3],所以返回 2 。

示例 2:

输入:nums = [1,2,3,4]
输出:1
解释:
子数组按位与运算的最大值是 4 。 
能得到此结果的最长子数组是 [4],所以返回 1 。

提示:

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

解题

方法一:脑筋急转弯

思路

根据按位与运算(&)的特性:a & b <= min(a, b) ,也就是说一个数组中任意子数组执行按位与运算后最大的结果一定是该数组中最大的值,而题目要求得到这个最大值的最长子数组长度,而要保持按位与的结果保持在最大值,只能选选取与数组中最大值相同的值来组成子数组。

那么这题就变成了:求一个数组中数组中的最大值最多连续出现了几次。

代码

class Solution {
    public int longestSubarray(int[] nums) {
        int max = 0;
        for (int num : nums) max = Math.max(num, max);
        int len = 0, maxLen = 1;
        for (int num : nums) {
            if (num == max) ++len;
            else {
                maxLen = Math.max(maxLen, len);
                len = 0;
            }
        }
        return Math.max(len, maxLen);
    }
}
class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int mx = *max_element(nums.begin(), nums.end());
        int len = 0, max_len = 1;
        for (int& num : nums) {
            if (num == mx) ++len;
            else {
                max_len = max(max_len, len);
                len = 0;
            }
        }
        return max(max_len, len);
    }
};
0

评论区