您的位置：首页 > 健康 > 美食 > 网站定制功能_公司设计说明_网络宣传方式有哪些_百度网站

网站定制功能_公司设计说明_网络宣传方式有哪些_百度网站

2024/12/27 13:22:20 来源：https://blog.csdn.net/DDDDWJDDDD/article/details/143605075  浏览:  次   关键词：网站定制功能_公司设计说明_网络宣传方式有哪些_百度网站
网站定制功能_公司设计说明_网络宣传方式有哪些_百度网站

目录

题目链接：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;// 初始化结果数组，默认值为 -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::vector<int> resultsArray(std::vector<int>& nums, int k) {// 获取数组长度int n = nums.size();// 初始化结果数组，默认值为 -1std::vector<int> 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::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   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 来控制和优化窗口的滑动逻辑。具体优化的地方主要在于减少大量不必要的判断和重复的计算。

优化的思路与实现：

  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   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:vector<int> resultsArray(vector<int>& nums, int k) {int n = nums.size();vector<int> 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;}
};

优化分析：

  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)，空间消耗主要来自结果数组。

对比：

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

版权声明:

本网仅为发布的内容提供存储空间，不对发表、转载的内容提供任何形式的保证。凡本网注明“来源：XXX网络”的作品，均转载自其它媒体，著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处。

我们尊重并感谢每一位作者，均已注明文章来源和作者。如因作品内容、版权或其它问题，请及时与我们联系，联系邮箱：809451989@qq.com，投稿邮箱：809451989@qq.com

最新新闻

热搜词

归来兮 百度竞价托管靠谱吗 springMVC-请求响应 营销相关笔记2：电力营销的业务办理和计量计费 PaddleOCR训练自己的私有数据集（包括标注、制作数据集、训练及应用） error类型及处理

声明：本站所有新闻及新闻图片来源于其他网站，如有侵权，请及时联系我们！

客户服务 | 关于我们 | 版权声明

版权所有：

Copyright 2024 尧图网 All Rights Reserved.QQ:809451989