503. 下一个更大元素 II

题目

给定一个循环数组 nums（nums[nums.length - 1] 的下一个元素是 nums[0]），返回 nums 中每个元素的下一个更大元素。

数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

示例 1:

输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；数字 2 找不到下一个更大的数；第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

示例 2:

输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]

提示:

1 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9

代码

完整代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>int* nextGreaterElements(int* nums, int numsSize, int* returnSize) {int *result = (int*)calloc(numsSize, sizeof(int));for (int i = 0; i < numsSize; i++) {bool findBigger = false;for (int j = 1; j < numsSize; j++) {int index = (i + j) % numsSize;if (nums[index] > nums[i]) {result[i] = nums[index];findBigger = true;break;}}if (!findBigger) {result[i] = -1;}}*returnSize = numsSize;return result;
}

思路分析

这套代码用了循环数组遍历的方法。

初始化结果数组 result，并设置其大小为 numsSize。
对于每个元素 nums[i]，从下一个元素开始循环搜索第一个比 nums[i] 大的元素。
使用双重循环，其中外层循环遍历每个元素，内层循环进行循环数组遍历。
如果找到更大的元素，则将其存入 result 中，否则将 -1 存入 result 中。

拆解分析

初始化结果数组

int *result = (int*)calloc(numsSize, sizeof(int));

初始化结果数组，大小为 numsSize，初始值为 0。

外层循环遍历每个元素

for (int i = 0; i < numsSize; i++) {bool findBigger = false;

外层循环遍历每个元素，findBigger 标志用于判断是否找到更大的元素。

内层循环进行循环数组遍历

for (int j = 1; j < numsSize; j++) {int index = (i + j) % numsSize;if (nums[index] > nums[i]) {result[i] = nums[index];findBigger = true;break;}
}

内层循环进行循环数组遍历，从下一个元素开始搜索第一个比 nums[i] 大的元素。

设置未找到更大元素时的结果

if (!findBigger) {result[i] = -1;
}

如果未找到更大的元素，则将 -1 存入 result 中。

复杂度分析

时间复杂度：O(n^2)，其中 n 为数组长度。双重循环导致时间复杂度为平方级别。
空间复杂度：O(n)，用于存储结果数组。

一题多解

方法2：单调栈解法

完整代码

#include <stdio.h>
#include <stdlib.h>int* nextGreaterElements(int* nums, int numsSize, int* returnSize) {int *result = (int*)calloc(numsSize, sizeof(int));int *stack = (int*)malloc(numsSize * sizeof(int));int top = -1;for (int i = 2 * numsSize - 1; i >= 0; i--) {int num = nums[i % numsSize];while (top != -1 && nums[stack[top]] <= num) {top--;}if (top == -1) {result[i % numsSize] = -1;} else {result[i % numsSize] = nums[stack[top]];}stack[++top] = i % numsSize;}*returnSize = numsSize;free(stack);return result;
}

思路分析

这套代码用了单调栈的方法。

单调栈的概念：
单调栈是一种特殊的栈数据结构，它保持栈内元素按某种顺序（如单调递减或单调递增）排列。在本问题中，我们使用单调递减栈，即栈内元素从栈底到栈顶是递减的。
遍历数组两次：
由于数组是循环的，我们需要遍历数组两次以确保每个元素都能找到其下一个更大元素。这是通过将遍历索引扩展到 2 * numsSize 来实现的。
栈的操作：
- 当遍历到一个元素时，检查当前元素与栈顶元素的大小。
- 如果当前元素大于栈顶元素，那么栈顶元素的下一个更大元素即为当前元素，将栈顶元素出栈并更新结果数组。
- 继续此过程直到栈为空或栈顶元素大于当前元素，然后将当前元素的索引入栈。
处理循环数组：
使用 i % numsSize 来获取实际元素的索引，从而处理数组的循环特性。

拆解分析

初始化结果数组和辅助栈

int *result = (int*)calloc(numsSize, sizeof(int));
int *stack = (int*)malloc(numsSize * sizeof(int));
int top = -1;

初始化结果数组和辅助栈，top 表示栈顶索引。

倒序遍历数组两次

for (int i = 2 * numsSize - 1; i >= 0; i--) {int num = nums[i % numsSize];while (top != -1 && nums[stack[top]] <= num) {top--;}if (top == -1) {result[i % numsSize] = -1;} else {result[i % numsSize] = nums[stack[top]];}stack[++top] = i % numsSize;
}

倒序遍历数组两次，使用单调栈存储元素索引，并更新结果数组。
下面是一个简单的测试用例的代码运行中情况：
用例：[1,5,3,8,4,6,7,9,2,5,6]

遍历次数	索引 `i`	元素 `nums[i % numsSize]`	栈 `stack`	结果 `result`
1	21	6	[10]	[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
1	20	5	[10, 9]	[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
1	19	2	[10, 9, 8]	[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
1	18	9	[10]	[-1, -1, -1, -1, -1, -1, -1, -1, -1, 6, -1]
1	17	7	[10, 8]	[-1, -1, -1, -1, -1, -1, -1, 9, -1, 6, -1]
1	16	6	[10, 8, 7]	[-1, -1, -1, -1, -1, -1, 9, 9, -1, 6, -1]
1	15	4	[10, 8, 7, 6]	[-1, -1, -1, -1, -1, 7, 9, 9, -1, 6, -1]
1	14	8	[10, 8]	[-1, -1, -1, -1, -1, 7, 9, 9, -1, 6, -1]
1	13	3	[10, 8, 5]	[-1, -1, -1, 8, -1, 7, 9, 9, -1, 6, -1]
1	12	5	[10, 8, 5, 4]	[-1, -1, 8, 8, -1, 7, 9, 9, -1, 6, -1]
1	11	1	[10, 8, 5, 4, 3]	[5, 8, 8, 8, -1, 7, 9, 9, -1, 6, -1]
2	10	6	[10]	[5, 8, 8, 8, -1, 7, 9, 9, -1, 6, -1]
2	9	5	[10, 9]	[5, 8, 8, 8, -1, 7, 9, 9, -1, 6, -1]
2	8	2	[10, 9, 8]	[5, 8, 8, 8, -1, 7, 9, 9, -1, 6, -1]
2	7	9	[10]	[5, 8, 8, 8, -1, 7, 9, 9, -1, 6, -1]
2	6	7	[10, 8]	[5, 8, 8, 8, -1, 7, 9, 9, -1, 6, -1]
2	5	6	[10, 8, 7]	[5, 8, 8, 8, -1, 7, 9, 9, -1, 6, -1]
2	4	4	[10, 8, 7, 6]	[5, 8, 8, 8, -1, 7, 9, 9, -1, 6, -1]
2	3	8	[10, 8]	[5, 8, 8, 8, -1, 7, 9, 9, -1, 6, -1]
2	2	3	[10, 8, 5]	[5, 8, 8, 8, -1, 7, 9, 9, -1, 6, -1]
2	1	5	[10, 8, 5, 4]	[5, 8, 8, 8, -1, 7, 9, 9, -1, 6, -1]
2	0	1	[10, 8, 5, 4, 3]	[5, 8, 8, 8, -1, 7, 9, 9, -1, 6, -1]