最长半递减数组

Submission

运行时间: 61 ms

内存: 29.6 MB

class Solution:
    def maxSubarrayLength(self, nums: List[int]) -> int:
        stack = []
        res = 0
        for i in reversed(range(len(nums))):
            if (len(stack) == 0 or nums[i] < nums[stack[-1]]):
                stack.append(i)


        for i in range(len(nums)): 

            while (stack and nums[i] > nums[stack[-1]]):
                popIdx = stack.pop()
                res = max(res, popIdx - i + 1)


        return res

Explain

这个解法利用了栈结构来保存数组中的元素下标。首先，遍历数组元素从右到左，将那些满足当前元素值小于栈顶元素值对应的数组元素的下标压入栈中。这样可以保证栈中元素下标对应的数组值是递减的。接着，从左到右遍历数组，每遇到一个元素，都尝试将栈顶的下标弹出，直到栈顶元素对应的数组值小于等于当前元素。对于每一个弹出的下标，计算当前位置与该下标的差，加1得到一个潜在的最长半递减数组的长度，并更新最大长度。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def maxSubarrayLength(self, nums: List[int]) -> int:
        stack = []  # 创建空栈用于存放下标
        res = 0  # 初始化结果变量
        for i in reversed(range(len(nums))):
            if (len(stack) == 0 or nums[i] < nums[stack[-1]]):
                stack.append(i)  # 压栈，仅当当前元素小于栈顶元素对应的数组值时


        for i in range(len(nums)): 

            while (stack and nums[i] > nums[stack[-1]]):
                popIdx = stack.pop()  # 弹出栈顶元素
                res = max(res, popIdx - i + 1)  # 更新最大长度


        return res  # 返回最大长度

Explore

这样设计的目的是为了确保栈中元素对应的数组索引从栈底到栈顶所对应的数组值是递减的。通过这种方式，可以保留每一段递减子数组的最远右侧的索引，这些索引在后续的左到右遍历中，可以帮助我们快速判断并找到与当前元素构成最长半递减数组的起始点。

从左到右遍历时，比较当前元素与栈顶元素对应的数组值的目的是为了找到一个合适的起始点，使得从该起始点到当前点的子数组是半递减的。当当前元素大于栈顶元素对应的数组值时，说明栈顶索引不再是一个有效的起始点，因为它与当前元素无法形成半递减关系。弹出栈顶元素后，栈中下一个元素将成为新的潜在起始点。这个过程帮助我们有效地维护和更新每次遍历的潜在最长半递减数组长度。

最长半递减数组定义为数组中的一个子数组，其中的元素从左到右至少是非递增的，即每个后续元素不大于前一个元素。在解法中，通过首先从右到左压栈递减元素索引，并在从左到右遍历时通过弹出不满足当前元素形成半递减关系的栈顶元素，可以确保每次计算的子数组段满足半递减的条件。

这里的加1是基于数组索引的计算特性。在数组中，两个索引的差值表示这两个索引之间有多少个元素间隔，但这不包括两端的元素。因此，要计算两端元素包括在内的总元素数量，需将索引差值加1。例如，如果起始索引是3，结束索引是5，则其差值为2，但实际上从索引3到5有3个元素（索引3, 4, 5），因此需要加1。