首页 > 其他分享 >力扣中等难度热题——长度为K的子数组的能量值

力扣中等难度热题——长度为K的子数组的能量值

时间：2024-11-07 20:19:17浏览次数：5  
标签：right nums int res 力扣 数组 热题 left

目录

题目链接：3255. 长度为 K 的子数组的能量值 II - 力扣（LeetCode）

题目描述

示例

提示：

解法一：通过连续上升的长度判断

Java写法：

C++写法：

 相比与Java写法的差别

运行时间

时间复杂度和空间复杂度

时间复杂度：

空间复杂度：

解法二：双指针+极限优化

优化前

Java写法：

优化前运行时间

优化后

优化的思路与实现：

Java写法：

C++写法：

优化分析：

运行时间

时间复杂度和空间复杂度

时间复杂度：

空间复杂度：

总结

解法一：通过连续上升的长度判断

解法二：双指针 + 极限优化

对比：

题目链接：3255. 长度为 K 的子数组的能量值 II - 力扣（LeetCode）

注：下述题目描述和示例均来自力扣

题目描述

给你一个长度为 n 的整数数组 nums 和一个正整数 k 。

一个数组的 能量值 定义为：

  • 如果 所有 元素都是依次 连续 且 上升 的，那么能量值为 最大 的元素。
  • 否则为 -1 。

你需要求出 nums 中所有长度为 k 的 子数组的能量值。

请你返回一个长度为 n - k + 1 的整数数组 results ，其中 results[i] 是子数组 nums[i..(i + k - 1)] 的能量值。

示例

示例 1：

输入：nums = [1,2,3,4,3,2,5], k = 3

输出：[3,4,-1,-1,-1]

解释：

nums 中总共有 5 个长度为 3 的子数组：

  • [1, 2, 3] 中最大元素为 3 。
  • [2, 3, 4] 中最大元素为 4 。
  • [3, 4, 3] 中元素 不是 连续的。
  • [4, 3, 2] 中元素 不是 上升的。
  • [3, 2, 5] 中元素 不是 连续的。

示例 2：

输入：nums = [2,2,2,2,2], k = 4

输出：[-1,-1]

示例 3：

输入：nums = [3,2,3,2,3,2], k = 2

输出：[-1,3,-1,3,-1]

提示：

  • 1 <= n == nums.length <= 10^{5}
  • 1 <= nums[i] <= 10^{6}
  • 1 <= k <= n

解法一：通过连续上升的长度判断

  • 初始化：

    • ans 数组用于存储每个长度为 k 的子数组的能量值，初始时设置所有值为 -1，因为默认情况下每个子数组的能量值是 -1。
    • cnt 用来记录当前子数组中连续上升的元素的个数。

  • 遍历数组：

    • 对于每个位置 i，我们检查 nums[i] 是否是连续上升序列的一部分。如果是，cnt 增加 1；如果不是，cnt 重置为 1。
    • 如果当前连续上升的元素数 cnt 达到 k，则说明当前位置的子数组 nums[i-k+1...i] 满足连续上升条件，并且它的能量值是当前的最大值，即 nums[i]。
    • 然后将该子数组的能量值保存在 ans[i - k + 1] 中。

  • 返回结果：

    • 最后返回结果数组 ans，它包含每个长度为 k 的子数组的能量值。

Java写法：

class Solution {
    public int[] resultsArray(int[] nums, int k) {
        // 获取数组长度
        int n = nums.length;
        // 初始化结果数组，默认值为 -1
        int[] res = new int[n - k + 1];
        // 初始化数组 res 所有元素为 -1
        Arrays.fill(res, -1);  
        
        // upLen 用来记录当前连续上升序列的长度
        int upLen = 0;
        
        // 遍历数组
        for (int i = 0; i < n; i++) {
            // 判断当前位置 nums[i] 是否是连续上升序列的一部分
            // 如果是，upLen 增加 1；如果不是，upLen 重置为 1
            if(i == 0 || nums[i] - nums[i - 1] != 1){
                upLen = 1;
            }else{
                upLen++;
            }
            // 如果当前连续上升的元素个数达到 k，更新对应子数组的能量值
            if (upLen >= k) {
                // 将该子数组的能量值（即最大元素 nums[i]）保存在 res 中
                res[i - k + 1] = nums[i];
            }
        }
        // 返回结果数组
        return res;
    }
}

C++写法：

#include <vector>
#include <algorithm>  // for std::fill

class Solution {
public:
    std::vector<int> resultsArray(std::vector<int>& nums, int k) {
        // 获取数组长度
        int n = nums.size();
        // 初始化结果数组，默认值为 -1
        std::vector<int> res(n - k + 1, -1);

        // upLen 用来记录当前连续上升序列的长度
        int upLen = 0;

        // 遍历数组
        for (int i = 0; i < n; i++) {
            // 判断当前位置 nums[i] 是否是连续上升序列的一部分
            // 如果是，upLen 增加 1；如果不是，upLen 重置为 1
            if (i == 0 || nums[i] - nums[i - 1] != 1) {
                upLen = 1;
            } else {
                upLen++;
            }

            // 如果当前连续上升的元素个数达到 k，更新对应子数组的能量值
            if (upLen >= k) {
                // 将该子数组的能量值（即最大元素 nums[i]）保存在 res 中
                res[i - k + 1] = nums[i];
            }
        }

        // 返回结果数组
        return res;
    }
};

 相比与Java写法的差别

  • vector：在 C++ 中，我们用 std::vector<int> 来代替 Java 中的数组，vector 是 C++ 中的动态数组容器。
  • std::fill：在 Java 中，我们使用 Arrays.fill 来填充数组，C++ 中对应的操作是 std::fill，不过在这里我们直接在初始化 vector 时提供了默认值 -1，因此不需要额外的 std::fill。
  • 数组大小：在 C++ 中，通过 nums.size() 获取数组的大小，n - k + 1 是结果数组的大小，表示有多少个长度为 k 的子数组。
  • 逻辑保持一致：其余的逻辑完全保留 Java 中的思路，主要是遍历数组，判断每个子数组是否满足“递增”条件，并更新结果数组。

运行时间

时间复杂度和空间复杂度

时间复杂度：

  1. 遍历数组：
    主要的操作是在遍历 nums 数组。遍历 nums 数组的时间复杂度是 O(n)，其中 n 是数组的长度。

  2. 更新结果数组：
    更新 res[i - k + 1] 的操作是常数时间操作 O(1)。每次更新时，我们只做简单的赋值操作。

因此，总的时间复杂度是 O(n)，其中 n 是输入数组 nums 的长度。

空间复杂度：

  1. 结果数组：
    需要一个大小为 n - k + 1 的数组 res 来存储最终结果。该数组的空间复杂度是 O(n - k + 1)，即 O(n)（因为 n - k + 1 的量级与 n 相同，忽略常数项）。

  2. 其他变量：
    除了结果数组，还使用了几个常数空间的变量（如 upLen 和 i）。这些是常数空间 O(1)。

因此，总的空间复杂度是 O(n)，因为主要的空间消耗来自结果数组 res。

解法二：双指针+极限优化

优化前

  • 双指针定义：

    • left 指针指向当前窗口的左边界，right 指针指向当前窗口的右边界。
    • 初始时，left = 0，right = k - 1，表示窗口包含了从 nums[0] 到 nums[k-1] 的元素。

  • 滑动窗口：

    • 每次通过右指针 right 来扩展窗口，在窗口内用指针 p 来判断该子数组是否是一个连续的上升序列。
    • 如果是连续的，结果数组 res[left] 记录下该子数组的最大值（即 nums[right]）。
    • 如果不是连续的，res[left] 标记为 -1。

  • 窗口后移：

    • 每次判断完一个窗口后，左指针 left 和右指针 right 都向右移动一位，继续判断下一个子数组。

Java写法：

class Solution {
    public int[] resultsArray(int[] nums, int k) {
        // k是大于1小于n的选手，我们直接诶采用双指针
        int left = 0;
        int right = k - 1;
        int n = nums.length;
        int[] res = new int[n - k + 1];
        // 1,2,3,4,3,2,5
        // l   r
        while(right < n){
            int p = right;
            // 使用p指针判断区间是否为连续的
            boolean flag = true;
            while(flag && p > left){
                // 如果不是连续的直接结束并标记flag
                if(nums[p] - nums[p - 1] != 1){
                    flag = false;
                    break;
                }
                // 没事就继续往下判断
                p--;
            }
            if(flag){
                // 证明是连续的,放入最大值
                res[left] = nums[right];
            }else{
                // 否则标记为-1
                res[left] = -1;
            }
            // 窗口区间后移
            left++;
            right++;
        }
        return res;
    }
}

优化前运行时间

        显然是没有通过的，那么我们就进入优化操作吧。

优化后

        我采用了标记变量 isOK 和 oldRight 来控制和优化窗口的滑动逻辑。具体优化的地方主要在于减少大量不必要的判断和重复的计算。

优化的思路与实现：

  1. isOK 标志位：

    • 你引入了 isOK 标志变量，用来判断当前的窗口是否满足是连续上升的状态。如果是连续的，就可以直接根据 oldRight（即上一个窗口的右端）来判断是否继续。如果连续，就可以跳过一些不必要的计算，减少了重复的检查。

  2. oldRight 的使用：

    • oldRight 用来记录上一个窗口右边界的元素值。当当前窗口的右边界的元素与 oldRight 连续时，直接跳过重复计算，直接赋值并移动窗口指针。

  3. 判断子数组是否是连续的：

    • 当 nums[right] - nums[left] != k - 1 时，直接返回 -1，标记当前子数组不符合条件，减少了不必要的判断。

  4. 通过 flag 判断连续性：

    • 内部的 while(flag) 判断窗口内是否是连续上升的子数组，如果是连续的，就将最大值（即 nums[right]）保存到结果数组中。

Java写法：

class Solution {
    public int[] resultsArray(int[] nums, int k) {
        // k是大于1小于n的选手，我们直接诶采用双指针
        int left = 0;
        int right = k - 1;
        int n = nums.length;
        int[] res = new int[n - k + 1];

        boolean isOK = false;
        int oldRight = -1;
        // 1,2,3,4,3,2,5
        // l   r
        while(right < n){
            if(isOK && nums[right] - oldRight == 1){
                res[left] = nums[right];
                // System.out.print("是我" + nums[right]);
                oldRight = nums[right];
                // 窗口区间后移
                left++;
                right++;
                continue;
            }

            oldRight = nums[right];
            int p = right;
            // 使用p指针判断区间是否为连续的
            boolean flag = true;

            if(nums[right] - nums[left] != k - 1){
                res[left] = -1;
                // 窗口区间后移
                left++;
                right++;

                isOK = false;
                continue;
            }

            while(flag && p > left){
                // 如果不是连续的直接结束并标记flag
                if(nums[p] - nums[p - 1] != 1){
                    flag = false;
                    break;
                }
                // 没事就继续往下判断
                p--;
            }
            if(flag){
                // 证明是连续的,放入最大值
                res[left] = nums[right];
                isOK = true;
            }else{
                isOK = false;
                // 否则标记为-1
                res[left] = -1;
            }
            // 窗口区间后移
            left++;
            right++;
        }
        return res;
    }
}

C++写法：

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> resultsArray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> res(n - k + 1, -1);  // 初始化结果数组，默认为-1
        
        int left = 0, right = k - 1;
        
        // 滑动窗口从左到右移动
        while (right < n) {
            int p = right;
            bool flag = true;
            
            // 判断当前窗口是否为连续的上升序列
            while (flag && p > left) {
                if (nums[p] - nums[p - 1] != 1) {
                    flag = false;
                    break;
                }
                p--;
            }
            
            if (flag) {
                // 如果是连续的，存储当前窗口的最大值，即 nums[right]
                res[left] = nums[right];
            } else {
                // 如果不是连续的，标记为-1
                res[left] = -1;
            }
            
            // 窗口后移
            left++;
            right++;
        }
        
        return res;
    }
};

优化分析：

  1. 减少重复计算：

    • 通过 isOK 标志位和 oldRight 变量，避免了对已满足条件的窗口的重复检查，提升了效率。

  2. 减少无效窗口判断：

    • 如果当前子数组不符合连续上升的条件（nums[right] - nums[left] != k - 1），直接标记为 -1，并跳过后续的连续性判断，减少了不必要的计算。

  3. 提高效率：

    • 通过引入 isOK 标志，避免了对窗口中已满足条件部分的重复计算，提高了整体的处理速度。

运行时间

时间复杂度和空间复杂度

时间复杂度：

  • 外层 while (right < n)：这个循环会遍历所有可能的窗口，每次窗口后移 1，最多运行 n - k + 1 次。
  • 内层 while(flag && p > left)：在最坏的情况下，内层循环最多会执行 k - 1 次（即窗口的最大长度）。因此，内层循环时间复杂度为 O(k)。

最终的时间复杂度是 O(n * k)，和之前的复杂度相似。

空间复杂度：

  • 主要空间消耗来自结果数组 res，其大小为 n - k + 1，所以空间复杂度为 O(n - k + 1)，即 O(n)。

 

总结

      那么我们就成功的解决连续上升子数组能量值问题的两种解法，并提供了 Java 和 C++ 代码实现。问题要求对于一个数组 nums，找到每个长度为 k 的子数组是否是连续上升的，如果是，则记录该子数组的最大值，否则标记为 -1。

解法一：通过连续上升的长度判断

  1. 思路：遍历数组，用 upLen 记录当前连续上升的元素个数。当 upLen 达到 k 时，记录该子数组的最大值到结果数组。
  2. 优点：简单，时间复杂度 O(n)，空间复杂度 O(n)。
  3. 实现：使用 Java 和 C++ 语言实现，逻辑相同，使用 std::vector 或数组来存储结果。

解法二：双指针 + 极限优化

  1. 思路：通过双指针 left 和 right 滑动窗口来判断每个子数组是否是连续上升的。引入 isOK 标志和 oldRight 来优化判断，减少不必要的计算。
  2. 优化：通过提前判断连续性，避免重复计算，提升效率。若当前子数组不满足条件，直接标记为 -1，跳过后续计算。
  3. 时间复杂度：O(n * k)，与解法一相似，但减少了重复判断。
  4. 空间复杂度：O(n)，空间消耗主要来自结果数组。

对比：

  • 解法一适合简单情况，容易实现，但效率较低。
  • 解法二通过优化滑动窗口的判断，减少了不必要的计算，提升了效率，适用于更大的输入数据。

标签：right,nums,int,res,力扣,数组,热题,left
From： https://blog.csdn.net/DDDDWJDDDD/article/details/143605075

相关文章

  • 后缀数组
    学了这个东西字符串水平下降一万倍，之前敢拿hash草的题现在不敢了。后缀数组板题后缀数组可以把字符串的所有后缀存起来，然后干各种奇怪的事情。现在给你一个字符串banana，给他的后缀A,NA,ANA,NANA,ANANA,BANANA跑一个后缀的trie。然后把字典序小的字母排在左边，给每个后缀对......
  • pyspark 解析kafka数组结构数据
    frompyspark.sql.functionsimportget_json_object,col,from_unixtime,instr,length,regexp_replace,explode,from_jsonfrompyspark.sql.typesimport*#定义数组结构schema=ArrayType(StructType([StructField("home",StringType()),S......
  • 力扣66.加一
    分三种情况（1）最后一位不是9（2）整个数字只有9（3）从最后一位到某一位数字都是9（1）很简单，最后一个数字++，然后输出整个数组（2）所有数字置为0，在数组最前面加一个1，使用insert函数       digits.insert(digits.begin(),1);insert使用方法见（3）从最后一位到第一个不是9的数......
  • js中类数组
    在JavaScript中，类数组（Array-likeObject）是指那些拥有类似数组的结构和特征，但并不真正是数组的对象。类数组对象有以下几个特征：具有length属性：类数组对象通常都有一个length属性，表示其元素的个数。可以通过整数索引访问元素：类数组对象的元素可以通过数字索引访问，类似于数......
  • 二维树状数组
    前置知识树状数组（不会就学一下再来）简介因为树状数组可以非常简洁解决序列上的一些问题，所以考虑能否用树状数组解决矩阵（二维序列）的问题。比较暴力的想法是对于每一横行建一个树状数组，再对每一列建一个树状数组统计答案。但这样显然要\(n+m\)个树状数组，但是我们发现这些树状数......
  • CUDA开始的GPU编程 - 第四章：C++封装GPU上的数组
    第四章：C++封装GPU上的数组std::vector的秘密：第二模板参数**你知道吗？**std::vector作为模板类，其实有两个模板参数：std::vector<T,AllocatorT>那为什么我们平时只用了std::vector呢？因为第二个参数默认是std::allocator。也就是std::vector等价于std::vector<T,s......
  • 华为OD机试真题-数组二叉树码-2024年OD统一考试（E卷）
    最新华为OD机试考点合集：华为OD机试2024年真题题库（E卷+D卷+C卷）_华为od机试题库-CSDN博客     每一题都含有详细的解题思路和代码注释，精编c++、JAVA、Python三种语言解法。帮助每一位考生轻松、高效刷题。订阅后永久可看，发现新题及时跟新。题目描述二叉树也可以用数组来......
  • SQL实战训练之，力扣：2020. 无流量的帐户数（递归）
    目录        一、力扣原题链接        二、题目描述        三、建表语句        四、题目分析                五、SQL解答        六、最终答案        七、验证        八、知识点一、......
  • 【C语言】实战-力扣题库：回文链表
    题目描述给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。提示：链表中节点数目在范围[1,105] 内0<=Node.val<=9进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？问题分析O(1)的时间复杂度---跟n......
  • LeetCode3264[K次乘运算后的最终数组I]
    题目链接LeetCode3264[K次乘运算后的最终数组I]详情实例实例1实例2提示题解思路先找到最小值然后对最小值进行操作最后输出容器代码classSolution{public:intfindVecMinNumIndex(vector<int>nums)//找出最小值的下标{inti=0,iMin......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99