739. 每日温度
https://programmercarl.com/0739.%E6%AF%8F%E6%97%A5%E6%B8%A9%E5%BA%A6.html
思路
int* dailyTemperatures(int* temperatures, int temperaturesSize, int* returnSize) {
int* answer = (int*)malloc(temperaturesSize * sizeof(int));
int* stack = (int*)malloc(temperaturesSize * sizeof(int));
int top = -1;
*returnSize = temperaturesSize; /
for (int i = 0; i < temperaturesSize; i++) {
answer[i] = 0;
}
for (int i = 0; i < temperaturesSize; i++) {
while (top != -1 && temperatures[i] > temperatures[stack[top]]) {
int idx = stack[top--];
answer[idx] = i - idx;
}
stack[++top] = i;
}
free(stack);
return answer;
}
学习反思
使用单调栈的思想来解决每日温度的问题。在遍历温度数组的过程中，我们使用一个栈来保存当前元素的索引。如果栈不为空且当前温度大于栈顶元素对应的温度，说明找到了栈顶元素的下一个更高温度，将栈顶元素弹出，并计算两个索引之间的距离，保存在答案数组中。最后将当前元素的索引压入栈中。代码中使用了两个指针top和i，top表示栈顶元素的索引，初始化为-1，i表示当前遍历到的温度数组的索引。同时，还使用了两个数组answer和stack，answer用来保存结果，stack用来保存温度数组元素的索引。在代码开头，通过malloc函数动态分配了两个数组的内存大小，并将temperaturesSize赋给了*returnSize。接下来，先将answer数组的所有元素初始化为0。然后，通过一个循环遍历温度数组，内部通过一个while循环来处理每个温度元素。在while循环中，如果栈不为空且当前温度大于栈顶元素对应的温度，就说明找到了栈顶元素的下一个更高温度，将栈顶元素弹出，并计算两个索引之间的距离，保存在答案数组中。最后将当前元素的索引压入栈中。最后，释放了栈的内存，并返回答案数组。这段代码使用了单调栈的思想来快速解决每日温度问题，时间复杂度为O(n)，空间复杂度为O(n)。
496.下一个更大元素 I
思路
int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
int* ans = (int*)malloc(nums1Size * sizeof(int));
int* nextGreater = (int*)malloc(10001 * sizeof(int));
for (int i = 0; i < 10001; i++) {
nextGreater[i] = -1;
}
int* stack = (int*)malloc(nums2Size * sizeof(int));
int top = -1;
for (int i = 0; i < nums2Size; i++) {
while (top != -1 && nums2[stack[top]] < nums2[i]) {
nextGreater[nums2[stack[top]]] = nums2[i];
top--;
}
stack[++top] = i;
}
for (int i = 0; i < nums1Size; i++) {
ans[i] = nextGreater[nums1[i]];
}
free(stack);
free(nextGreater);
*returnSize = nums1Size;
return ans;
}
学习反思
使用单调栈的思想来解决下一个更大元素的问题。给定两个数组nums1和nums2，要求在nums2中找到nums1中每个元素的下一个更大元素。代码中使用了一个辅助数组nextGreater，用来保存每个元素的下一个更大元素。数组的大小设为10001，原因是nums2中的元素范围在0到10000之间。在代码开头，通过malloc函数动态分配了两个数组的内存大小，并将nums1Size赋给了*returnSize。接着，通过一个循环将nextGreater数组的所有元素初始化为-1。然后，通过一个循环遍历nums2数组，内部通过一个while循环来处理每个元素。在while循环中，如果栈不为空且栈顶元素对应的值小于当前元素的值，就说明找到了栈顶元素的下一个更大元素，将栈顶元素弹出，并将当前元素的值赋给对应的nextGreater数组元素。最后将当前元素的索引压入栈中。然后，通过一个循环遍历nums1数组，将每个元素对应的下一个更大元素从nextGreater数组中取出并保存在答案数组ans中。最后，释放了栈和nextGreater数组的内存，并返回答案数组。这段代码使用了单调栈的思想来快速解决下一个更大元素的问题，时间复杂度为O(m+n)，其中m和n分别为nums1和nums2的长度。空间复杂度为O(m+n)。
503.下一个更大元素II
思路
int* nextGreaterElements(int* nums, int numsSize, int* returnSize) {
int* ans = (int*)malloc(numsSize * sizeof(int));
for (int i = 0; i < numsSize; i++) {
ans[i] = -1; }
int* stack = (int*)malloc(numsSize * sizeof(int));
int top = -1;
for (int i = 0; i < 2 * numsSize; i++) {
int currentIndex = i % numsSize;
while (top != -1 && nums[currentIndex] > nums[stack[top]]) {
ans[stack[top]] = nums[currentIndex];
top--;
}
if (i < numsSize) {
stack[++top] = currentIndex;
}
}
free(stack);
*returnSize = numsSize;
return ans;
}学习反思
实现了一个函数，用于找到数组中每个元素的下一个更大元素。函数输入一个整数数组nums，数组大小为numsSize，输出一个大小为numsSize的整数数组ans，其中ans[i]表示nums[i]的下一个更大的元素，如果不存在则为-1。这个函数的实现使用了单调栈的思想。首先，初始化ans数组，将每个元素都设置为-1。然后，创建一个数组stack和一个变量top，用于实现单调栈的操作。遍历2 * numsSize次，以保证循环可以回到起点。在每次循环中，通过取余操作获取当前元素的实际索引。然后，通过一个while循环，从栈顶开始比较当前元素和栈顶元素，如果当前元素大于栈顶元素，则将栈顶元素在ans数组中对应的位置设置为当前元素，并将栈顶指针top减1。这是因为栈顶元素的下一个更大元素已经找到了。接下来，如果当前循环次数小于numsSize，表示还有元素尚未入栈。此时，将当前元素的索引入栈，并将top指针加1。循环结束后，释放栈的内存，将returnSize指向numsSize，最后返回ans数组。这段代码的时间复杂度为O(n)，其中n为nums数组的大小。空间复杂度为O(n)，主要是用于存储ans和stack数组。
总结
加油！！！
标签：int,栈顶,top,元素,随想录,第四十七,数组,Day47,stack From： https://blog.csdn.net/a6666999d/article/details/143806445