@ 代码随想录算法训练营第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;
}