乘积为正数的最长子数组长度
难度:
标签:
题目描述
代码结果
运行时间: 65 ms, 内存: 29.6 MB
/*
* 思路:
* 使用Java Stream API可能并不是处理这种问题的最佳选择,因为Stream API更适用于处理集合或数组中的独立元素,而不是需要维护状态的连续子数组问题。
* 但是我们可以尝试用forEach来处理数组。
*/
import java.util.Arrays;
public class Solution {
public int getMaxLen(int[] nums) {
int[] result = {0};
int[] posLen = {0}; // 当前乘积为正数的长度
int[] negLen = {0}; // 当前乘积为负数的长度
Arrays.stream(nums).forEach(num -> {
if (num > 0) {
posLen[0]++;
negLen[0] = (negLen[0] > 0) ? negLen[0] + 1 : 0;
} else if (num < 0) {
int temp = posLen[0];
posLen[0] = (negLen[0] > 0) ? negLen[0] + 1 : 0;
negLen[0] = temp + 1;
} else { // num == 0
posLen[0] = 0;
negLen[0] = 0;
}
result[0] = Math.max(result[0], posLen[0]);
});
return result[0];
}
}
解释
方法:
这个题解利用了一种遍历和记录策略,使用了栈来记录负数的索引位置。首先,代码在数组末尾添加了一个0作为哨兵值,以便处理到达数组末尾的情况。接着,通过遍历数组,记录每个非零元素的长度,同时记录遇到的负数的位置。当遇到0或者到达数组末尾时,根据栈中负数的数量决定如何计算最长的乘积为正的子数组长度。如果负数数量为偶数,整个区间乘积为正,直接更新最长长度。如果为奇数,则需要去掉一个负数,以确保子数组乘积为正,通常有两种去除方式:去掉最左边或最右边的负数,这取决于哪种方式能保留更长的子数组。最后,返回记录的最大长度。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么需要在数组末尾添加一个0作为哨兵值,这对算法有什么具体帮助?
▷🦆
在栈中记录负数索引的目的是什么,这与算法如何处理负数个数相关?
▷🦆
当栈中负数个数为奇数时,为什么选择去掉最左边或最右边的负数,这种选择是如何影响子数组长度的?
▷🦆
如何处理数组中连续的0的情况,连续0是否会影响到子数组长度的计算?
▷