当前位置：首页 > article >正文

代码随想录算法训练营第四十七天|Day47 单调栈

article 2024/11/19 2:39:35

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

https://programmercarl.com/0496.%E4%B8%8B%E4%B8%80%E4%B8%AA%E6%9B%B4%E5%A4%A7%E5%85%83%E7%B4%A0I.html

思路


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

https://programmercarl.com/0503.%E4%B8%8B%E4%B8%80%E4%B8%AA%E6%9B%B4%E5%A4%A7%E5%85%83%E7%B4%A0II.html

思路

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数组。