leetcode
leetcode 1951 ~ 2000
使数组按非递减顺序排列

使数组按非递减顺序排列

难度:

标签:

题目描述

代码结果

运行时间: 158 ms, 内存: 30.1 MB


// 思路:通过Stream API的使用来简化操作。我们仍然需要移除所有的下降点,使数组变为非递减。
// 实现方式:使用Stream API和过滤器过滤掉不满足条件的部分。然后计算每次操作的次数。

import java.util.Arrays;

public class Solution {
    public int countOperations(int[] nums) {
        int operations = 0;
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int i = 1; i < nums.length; i++) {
                if (nums[i - 1] > nums[i]) {
                    nums = Arrays.stream(nums)
                        .filter(n -> n >= nums[i])
                        .toArray();
                    changed = true;
                    operations++;
                    break;
                }
            }
        }
        return operations;
    }
}

解释

方法:

该题解采用了单调栈和动态规划的结合方式。首先,初始化一个空栈和一个动态规划数组dp,dp[i]用于记录以nums[i]为起点,数组需要经过的删除步骤数。从数组的末尾开始向前遍历,对于每个元素nums[i],检查栈顶元素representing the indices of elements in the array。如果栈不为空且nums[i]大于栈顶元素对应的数组值,说明nums[i]能在一次操作中保留下来而栈顶元素会被删除,此时将栈顶元素出栈,并更新dp[i]为max(dp[i] + 1, dp[栈顶元素]),意味着nums[i]能延续的删除步骤至少是之前的步骤加一或者栈顶元素的步骤。将每个元素的索引最终压入栈中。最后,返回dp数组中的最大值,即为整个数组变为非递减数组所需的最大删除步骤数。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在算法中使用单调栈而不是其他数据结构,比如数组或链表?
单调栈的特点是能够在O(1)的时间复杂度内访问到需要比较的元素,并且能够在O(1)的时间复杂度内添加和删除元素。在本算法中,需要频繁地进行元素比较和删除操作,单调栈可以高效地处理这些操作,保证整体算法的效率。相比之下,如果使用数组或链表,虽然也可以实现相同的功能,但在删除元素时可能需要更高的时间复杂度,特别是数组在删除元素后还需要处理元素的移动,效率较低。
🦆
算法中的动态规划数组dp是如何初始化的,为什么所有元素初始值都是0?
动态规划数组dp用于记录每个位置i所需的最小删除步骤数,使得从该位置到数组末尾的子数组成为非递减序列。初始化所有元素的值为0是因为每个元素本身不需要任何删除操作就可以作为长度为1的非递减序列,即在最初的情况下,没有需要删除的其他元素,所以初始步骤数为0。
🦆
在循环中,`while stk and nums[i] > nums[stk[-1]]:` 这个条件是如何确保数组变为非递减的?
这个条件用于检查当前元素nums[i]是否大于栈顶元素对应的数组值。如果是,这意味着为了保持非递减序列,栈顶元素(较小的元素)需要被删除,因为它位于当前元素(较大的元素)之后。通过这种方式,算法逐步从数组末尾向前确保任何时刻栈内的元素对应的数组值都是非递减的。每次循环检查和可能的删除操作都是为了维持这个非递减的性质。
🦆
为什么每次处理元素时,需要更新`dp[i] = max(dp[i] + 1, dp[stk.pop()])`,这里的逻辑是基于什么考虑?
这里的更新逻辑是为了确保dp[i]记录的是以nums[i]为起点所需的最大删除步骤数。当nums[i]大于栈顶元素时,栈顶元素需要被删除,此时dp[i]应至少为栈顶元素的dp值加1(表示除了栈顶元素外还可能需要更多的删除步骤)。使用max函数是为了处理可能的多个栈顶元素被连续删除的情况,确保dp[i]始终是正确的最大步骤数。

相关问题