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

初始化：
- 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 中的思路，主要是遍历数组，判断每个子数组是否满足“递增”条件，并更新结果数组。

运行时间

时间复杂度和空间复杂度

时间复杂度：

遍历数组：
主要的操作是在遍历 nums 数组。遍历 nums 数组的时间复杂度是 O(n)，其中 n 是数组的长度。
更新结果数组：
更新 res[i - k + 1] 的操作是常数时间操作 O(1)。每次更新时，我们只做简单的赋值操作。

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

空间复杂度：

结果数组：
需要一个大小为 n - k + 1 的数组 res 来存储最终结果。该数组的空间复杂度是 O(n - k + 1)，即 O(n)（因为 n - k + 1 的量级与 n 相同，忽略常数项）。
其他变量：
除了结果数组，还使用了几个常数空间的变量（如 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 来控制和优化窗口的滑动逻辑。具体优化的地方主要在于减少大量不必要的判断和重复的计算。

优化的思路与实现：

isOK 标志位：
- 你引入了 isOK 标志变量，用来判断当前的窗口是否满足是连续上升的状态。如果是连续的，就可以直接根据 oldRight（即上一个窗口的右端）来判断是否继续。如果连续，就可以跳过一些不必要的计算，减少了重复的检查。
oldRight 的使用：
- oldRight 用来记录上一个窗口右边界的元素值。当当前窗口的右边界的元素与 oldRight 连续时，直接跳过重复计算，直接赋值并移动窗口指针。
判断子数组是否是连续的：
- 当 nums[right] - nums[left] != k - 1 时，直接返回 -1，标记当前子数组不符合条件，减少了不必要的判断。
通过 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;
    }
};

优化分析：

减少重复计算：
- 通过 isOK 标志位和 oldRight 变量，避免了对已满足条件的窗口的重复检查，提升了效率。
减少无效窗口判断：
- 如果当前子数组不符合连续上升的条件（nums[right] - nums[left] != k - 1），直接标记为 -1，并跳过后续的连续性判断，减少了不必要的计算。
提高效率：
- 通过引入 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。

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

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

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

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

对比：

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

原文地址：https://blog.csdn.net/DDDDWJDDDD/article/details/143605075

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

常用基础数据库表
LANGUAGE_KEY` varchar(50) DEFAULT NULL COMMENT '国际化语言KEY',`SORT` bigint(5) NOT NULL DEFAULT '0' COMM
阅读更多2024-11-13
在colab中把微调后的大模型合并和量化——仅作参考
前提，在我的云端硬盘创建文件夹colab，然后上传两个压缩文件。解压模型Qwen2.5-1.5B-Instruct.zip。新建colab，修改笔记本设置，然后连接。解压just_train.zip。
阅读更多2024-11-13
LeetCode 二分算法范围内整数的最大得分
LeetCode 二分算法范围内整数的最大得分
阅读更多2024-11-13
shell第三章（条件测试）
注释：用来判断id root是否存在，存在则没有信息录入/dev/null(类似于空洞)，则表示为真，没有此用户，则会用内容录入/dev/null，从而为假。注释：who：用来查看当前有多少用户进行
阅读更多2024-11-13
tartanvo ubuntu 20.04部署
【代码】tartanvo ubuntu 20.04部署。
阅读更多2024-11-13
Ubuntu 的 ROS 操作系统turtlebot3环境搭建
本文介绍了如何在Ubuntu 20.04系统上为TurtleBot3配置ROS Noetic环境。通过详细的步骤，包括下载和安装Ubuntu、安装ROS Noetic、配置依赖包以及设置网络，帮助用户
阅读更多2024-11-13
网络安全-HTML基础
web基础之HTML超文本表示网络安全红队大佬（成长ing）,学习分享
阅读更多2024-11-13
手把手写深度学习(29)：将DDP训练代码改成DeepSpeed
deepspeed已经成为了大模型时代训练模型的常规武器，这篇博客以一个基于DDP的 Stable Diffusion模型训练为例，讲解如何从将DDP训练代码改成DeepSpeed。
阅读更多2024-11-13
人工智能的现状、应用与面临的挑战
近年来，人工智能（AI）在计算能力和算法上的进展使其成为技术变革的引擎。在越来越多的场景中，AI不仅改变了工作方式，也逐渐进入日常生活，成为科技发展的标志性成果。尽管如此，AI在发展的过程中仍然面临技
阅读更多2024-11-13
candence : 原理图中如何设置差分对？
1、选中一个原理图，如下图所示。2、根据需要进行设置。
阅读更多2024-11-13

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

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

题目描述

示例

提示：

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

Java写法：

C++写法：

相比与Java写法的差别

运行时间

时间复杂度和空间复杂度

时间复杂度：

空间复杂度：

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

优化前

Java写法：

优化前运行时间

优化后

优化的思路与实现：

Java写法：

C++写法：

优化分析：

运行时间

时间复杂度和空间复杂度

时间复杂度：

空间复杂度：

总结

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

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

对比：

相关文章