正阳县网站建设,一个商城网站多少钱,app软件开发外包公司,建筑人才网官网 北京目录
题目链接#xff1a;3255. 长度为 K 的子数组的能量值 II - 力扣#xff08;LeetCode#xff09;
题目描述
示例
提示#xff1a;
解法一#xff1a;通过连续上升的长度判断
Java写法#xff1a;
C写法#xff1a; 相比与Java写法的差别
运行时间
时间复杂…
目录
题目链接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 1 nums[i] 1 k n 解法一通过连续上升的长度判断 初始化 ans 数组用于存储每个长度为 k 的子数组的能量值初始时设置所有值为 -1因为默认情况下每个子数组的能量值是 -1。cnt 用来记录当前子数组中连续上升的元素的个数。 遍历数组 对于每个位置 i我们检查 nums[i] 是否是连续上升序列的一部分。如果是cnt 增加 1如果不是cnt 重置为 1。如果当前连续上升的元素数 cnt 达到 k则说明当前位置的子数组 nums[i-k1...i] 满足连续上升条件并且它的能量值是当前的最大值即 nums[i]。然后将该子数组的能量值保存在 ans[i - k 1] 中。 返回结果 最后返回结果数组 ans它包含每个长度为 k 的子数组的能量值。 Java写法
class Solution {public int[] resultsArray(int[] nums, int k) {// 获取数组长度int n nums.length;// 初始化结果数组默认值为 -1int[] res new int[n - k 1];// 初始化数组 res 所有元素为 -1Arrays.fill(res, -1); // upLen 用来记录当前连续上升序列的长度int upLen 0;// 遍历数组for (int i 0; i n; i) {// 判断当前位置 nums[i] 是否是连续上升序列的一部分// 如果是upLen 增加 1如果不是upLen 重置为 1if(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::fillclass Solution {
public:std::vectorint resultsArray(std::vectorint nums, int k) {// 获取数组长度int n nums.size();// 初始化结果数组默认值为 -1std::vectorint res(n - k 1, -1);// upLen 用来记录当前连续上升序列的长度int upLen 0;// 遍历数组for (int i 0; i n; i) {// 判断当前位置 nums[i] 是否是连续上升序列的一部分// 如果是upLen 增加 1如果不是upLen 重置为 1if (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::vectorint 来代替 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 0right 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 rwhile(right n){int p right;// 使用p指针判断区间是否为连续的boolean flag true;while(flag p left){// 如果不是连续的直接结束并标记flagif(nums[p] - nums[p - 1] ! 1){flag false;break;}// 没事就继续往下判断p--;}if(flag){// 证明是连续的,放入最大值res[left] nums[right];}else{// 否则标记为-1res[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 rwhile(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){// 如果不是连续的直接结束并标记flagif(nums[p] - nums[p - 1] ! 1){flag false;break;}// 没事就继续往下判断p--;}if(flag){// 证明是连续的,放入最大值res[left] nums[right];isOK true;}else{isOK false;// 否则标记为-1res[left] -1;}// 窗口区间后移left;right;}return res;}
}
C写法
#include vector
using namespace std;class Solution {
public:vectorint resultsArray(vectorint nums, int k) {int n nums.size();vectorint res(n - k 1, -1); // 初始化结果数组默认为-1int 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 {// 如果不是连续的标记为-1res[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)空间消耗主要来自结果数组。
对比
解法一适合简单情况容易实现但效率较低。解法二通过优化滑动窗口的判断减少了不必要的计算提升了效率适用于更大的输入数据。
