LeetCode1909 删除一个元素使数组严格递增

判断删除一个元素后数组是否可变为严格递增

一、问题描述

在编程中，我们有时会遇到这样一个有趣的问题：给定一个下标从 0 开始的整数数组 nums，我们需要判断是否恰好删除一个元素后，该数组可以变成严格递增的，或者如果数组本身已经是严格递增的，也满足条件。这里对于严格递增的定义是对于任意下标的 1 <= i < nums.length 都满足 nums[i - 1] < nums[i]。

二、解决思路

为了解决这个问题，我们主要分为两步：

检查原数组是否严格递增：
我们编写了一个辅助函数 isStrictlyIncreasing，该函数接收一个整数数组 nums 和数组的长度 numsSize。其核心思想是遍历数组，从第二个元素开始，将其与前一个元素进行比较。如果发现存在 nums[i - 1] >= nums[i] 的情况，说明原数组不是严格递增的，函数将返回 false。若遍历完整个数组都满足 nums[i - 1] < nums[i] 的条件，函数将返回 true。
```
#include <stdio.h>
#include <stdlib.h>// 检查数组是否严格递增
bool isStrictlyIncreasing(int* nums, int numsSize) {for (int i = 1; i < numsSize; i++) {if (nums[i - 1] >= nums[i]) {return false;}}return true;
}
```
尝试删除元素并检查：
如果原数组不是严格递增的，我们需要尝试删除每一个元素，然后检查删除该元素后的数组是否严格递增。为此，我们编写了 canBeIncreasing 函数。该函数首先调用 isStrictlyIncreasing 检查原数组。若原数组满足条件，直接返回 true。若不满足，我们使用 for 循环遍历原数组的每个元素。对于每个元素，我们创建一个新的临时数组 temp，使用 malloc 分配 (numsSize - 1) * sizeof(int) 大小的内存空间。然后使用另一个 for 循环将原数组中除了当前元素外的元素复制到 temp 中，使用 index 变量来记录复制元素的位置。接着调用 isStrictlyIncreasing 函数检查这个临时数组是否严格递增。若满足，释放 temp 的内存并返回 true。若遍历完所有元素的删除情况都不满足，最终返回 false。
```
bool canBeIncreasing(int* nums, int numsSize) {if (isStrictlyIncreasing(nums, numsSize)) {return true;}for (int i = 0; i < numsSize; i++) {int* temp = (int*)malloc((numsSize - 1) * sizeof(int));int index = 0;for (int j = 0; j < numsSize; j++) {if (j!= i) {temp[index++] = nums[j];}}if (isStrictlyIncreasing(temp, numsSize - 1)) {free(temp);return true;}free(temp);}return false;
}
```
三、代码解释

isStrictlyIncreasing 函数：

该函数的目的是判断一个数组是否严格递增。
从 i = 1 开始遍历数组，比较 nums[i - 1] 和 nums[i] 的大小。
只要发现 nums[i - 1] >= nums[i]，说明不满足严格递增的条件，函数返回 false。
若整个遍历过程都满足条件，函数最终返回 true。

canBeIncreasing 函数：

首先调用 isStrictlyIncreasing 函数对原数组进行检查。
若原数组是严格递增的，函数直接返回 true。
若原数组不满足，开始遍历原数组的元素，准备删除每个元素进行尝试。
对于每个元素的删除，创建一个新的临时数组 temp，通过 malloc 分配内存。
将原数组中除当前元素外的元素复制到 temp 中，使用 index 来控制存储位置。
对 temp 调用 isStrictlyIncreasing 函数进行检查。
若满足，释放 temp 的内存并返回 true。
若遍历完都不满足，最终返回 false，同时注意释放内存以避免内存泄漏。

四、测试示例

为了测试我们的函数，我们可以编写一个简单的 main 函数：

int main() {int nums[] = {1, 2, 10, 5, 7};int numsSize = sizeof(nums) / sizeof(nums[0]);if (canBeIncreasing(nums, numsSize)) {printf("True\n");} else {printf("False\n");}return 0;
}