@ 代码随想录算法训练营第9周（C语言）|Day62（单调栈）

@ 代码随想录算法训练营第9周（C语言）|Day62（单调栈）

Day25、回溯（包含题目 739. 每日温度 496.下一个更大元素 I ）

739. 每日温度

题目描述

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

题目解答

int* dailyTemperatures(int* temperatures, int temperaturesSize, int* returnSize) {
    int stack[1000000];
    int stacksize=1;
    stack[0]=0;
    int * res=(int *)malloc(sizeof(long int)*temperaturesSize);
    int k=0;
    //memset(res,0,sizeof(res));
    for(int i=0;i<temperaturesSize;i++){
        res[i]=0;
    }
    for(int i=1;i<temperaturesSize;i++){
        while(stacksize!=0){
            if(temperatures[stack[stacksize-1]]<temperatures[i]){
                res[stack[stacksize-1]]=i-stack[stacksize-1];
                stacksize--;
            }else{
                stack[stacksize++]=i;
                break;
            }
            
        }
        stack[stacksize++]=i;
        
        
        
    }
    (*returnSize)=temperaturesSize;
    return res;
}

题目总结

找当前数组比当前元素大的数，使用单调递增的单调栈。

496.下一个更大元素 I

题目描述

给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。

请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

题目解答

int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    int n=nums1Size;
    int m=nums2Size;
    *returnSize=n;
    int hash[10001];
    memset(hash,0,sizeof(hash));

    int* res=(int*)malloc(sizeof(int)*n);
    int *stack=(int*)malloc(sizeof(int)*m);
    int top=0;
    stack[top++]=0;

    for(int i=1;i<m;i++){
        if(nums2[i]>nums2[stack[top-1]]){
            while(top>0&&nums2[i]>nums2[stack[top-1]]){
                hash[nums2[stack[top-1]]]=i;//记录比当前坐标元素大的元素坐标
                top--;
            }
        }
        stack[top++]=i;
    }
    for(int i=0;i<n;i++){
        res[i]=hash[nums1[i]]==0?-1:nums2[hash[nums1[i]]];
    }
    return res;
}

题目总结

使用hash进行快速查找元素坐标。