leetcode
leetcode 1401 ~ 1450
乘积为正数的最长子数组长度

乘积为正数的最长子数组长度

难度:

标签:

题目描述

代码结果

运行时间: 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为分隔符的逻辑,无论数组最后一个元素是否为0。这避免了在循环结束后还需要额外的逻辑来处理最后一个非零子数组的情况。简而言之,哨兵0可以作为一个自然的终止标记,让代码更简洁且易于理解。
🦆
在栈中记录负数索引的目的是什么,这与算法如何处理负数个数相关?
在栈中记录负数索引的目的是为了在处理遇到的0时能够快速定位到当前非零子数组中所有负数的位置。这样做有助于快速计算当前子数组中负数的总数,并根据负数的奇偶性决定子数组的乘积正负。如果负数个数为偶数,则整个子数组的乘积为正;如果为奇数,则需要移除一个负数以确保乘积为正。通过栈来记录负数位置,可以有效地实现这一逻辑处理,特别是在需要计算移除某个负数后子数组长度的情况。
🦆
当栈中负数个数为奇数时,为什么选择去掉最左边或最右边的负数,这种选择是如何影响子数组长度的?
当栈中负数个数为奇数时,为了使子数组的乘积变为正,必须移除一个负数。选择去掉最左边或最右边的负数是为了最大化剩余子数组的长度。具体地,如果移除最左边的负数,则子数组从最左边负数的下一个位置开始到当前段的结束;如果移除最右边的负数,则子数组从当前段的开始到最右边负数的前一个位置结束。比较这两种方式后,选择可以保留更长子数组的方案。这种策略确保了在保持乘积为正的前提下,所得到的子数组尽可能长。
🦆
如何处理数组中连续的0的情况,连续0是否会影响到子数组长度的计算?
在数组中遇到连续的0时,每个0都会被视为一个新的分隔符,即它们各自独立地终止前一个非零子数组的计算,并重置后续非零子数组的起始点。因此,连续的0将导致多次重置子数组的长度和负数索引栈。这意味着每段非零子数组都是独立计算和评估的,连续的0之间不会有任何子数组长度的累加或传递。这种处理保证了算法的正确性和逻辑的清晰。

相关问题