当前位置：首页 > news >正文

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

news 2024/11/8 0:10:13

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

运行时间

时间复杂度和空间复杂度

时间复杂度：

遍历数组：
主要的操作是在遍历 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   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: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;}
};

优化分析：

减少重复计算：
- 通过 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)，空间消耗主要来自结果数组。