目录思路model例题例题739 - 每日温度 mid例题496 - 下一个更大元素Ⅰeasy例题503 - 下一个更大元素Ⅱ mid例题42 - 接雨水 hard例题84 - 柱状图中最大矩阵 hard学习代码随想录题源LeetCode思路某元素左边或右边第一个比当前元素大或小的元素单调栈的栈内元素保持单调递增或递减的顺序按照从栈顶-栈底model// ans记录结果int* ans;// 单调栈初始化int* stk;int top 0;stk[0] nums[0[;// 一次遍历 --- 下标压栈for(int i 1; inumsSize; i){while(top0 nums[i]nums[stk[top]]){// 处理ans[stk[top]] nums[i];top--;}stk[top] i;}// return*returnSize numsSize;return ans;例题例题739 - 每日温度mid给定一个整数数组temperatures表示每天的温度返回一个数组answer其中answer[i]是指对于第i天下一个更高温度出现在几天后。如果气温在这之后都不会升高请在该位置用0来代替。单增栈找下一个更高温度--元素压栈遇到比栈顶大的出栈然后当前元素压栈几天后--栈中存放下标ans中记录当前下标-出栈下标/** * Note: The returned array must be malloced, assume caller calls free(). */ int* dailyTemperatures(int* temperatures, int temperaturesSize, int* returnSize) { // init stk int* ans calloc(temperaturesSize, sizeof(int)); int* stk calloc(temperaturesSize, sizeof(int)); int top -1; // 采用实心也就是top指向有数据的 stk[top] 0; for(int i 1; itemperaturesSize; i){ while(top0 temperatures[i]temperatures[stk[top]]){ // 当栈非空且当前元素的值大于栈顶元素 int idx stk[top]; // 出栈下标ans要记录的下标 ans[idx] i-idx; // ans记录 top--; // 出栈 } stk[top] i; // 新元素入栈 } *returnSize temperaturesSize; return ans; }例题496 - 下一个更大元素Ⅰeasynums1中数字x的下一个更大元素是指x在nums2中对应位置右侧的第一个比x大的元素。给你两个没有重复元素的数组nums1和nums2下标从0开始计数其中nums1是nums2的子集。对于每个0 i nums1.length找出满足nums1[i] nums2[j]的下标j并且在nums2确定nums2[j]的下一个更大元素。如果不存在下一个更大元素那么本次查询的答案是-1。返回一个长度为nums1.length的数组ans作为答案满足ans[i]是如上所述的下一个更大元素。单增栈hash表和单调栈结合思路一① hash元素初始化-1记录nums1元素对应下标或初始化0下标1防止下标0的情况② 对nums2遍历使用单增栈得到各元素对应下一个最大元素③ 然后判断是否在hash即nums1里面加入ans思路二① hash元素初始化-1② 对nums2遍历使用单增栈得到各元素对应下一个最大元素记录在hash表中③ 遍历nums1元素对应hash表中值即下一个最大元素加入ans// way1 int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) { int* hash calloc(10001, sizeof(int)); for(int i 0; inums1Size; i){ hash[nums1[i]] i1; // 初始化hash为-1不用加该1 } int* ans malloc(nums1Size*sizeof(int)); memset(ans, -1, nums1Size*sizeof(int)); int* stk calloc(nums2Size, sizeof(int)); int top 0; stk[0] 0; for(int i 1; inums2Size; i){ while(top0 nums2[i]nums2[stk[top]]){ int x hash[nums2[stk[top]]]; if(x){ ans[x-1] nums2[i]; // 初始化hash为-1不用减该1 } top--; } stk[top] i; // 下标压栈 } *returnSize nums1Size; return ans; } // way2 int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) { int hash[10001]; memset(hash, -1, sizeof(hash)); int* ans malloc(sizeof(int)*nums1Size); int* stk calloc(nums2Size, sizeof(int)); int top 0; stk[0] nums2[0]; for(int i 1; inums2Size; i){ while(top0 nums2[i]stk[top]){ hash[stk[top]] nums2[i]; top--; } stk[top] nums2[i]; // 元素压栈 } for(int i 0; inums1Size; i){ ans[i] hash[nums1[i]]; } *returnSize nums1Size; return ans; }例题503 - 下一个更大元素Ⅱmid给定一个循环数组numsnums[nums.length - 1]的下一个元素是nums[0]返回nums中每个元素的下一个更大元素。数字x的下一个更大的元素是按数组遍历顺序这个数字之后的第一个比它更大的数这意味着你应该循环地搜索它的下一个更大的数。如果不存在则输出-1。单增栈循环数组用模运算实现int* nextGreaterElements(int* nums, int numsSize, int* returnSize) { int* ans malloc(sizeof(int)*numsSize); memset(ans, -1, sizeof(int)*numsSize); int stk[numsSize*2]; memset(stk, 0, sizeof(stk)); stk[0] 0; int top 0; for(int i 1; inumsSize*2; i){ // 遍历两次然后i对numsSize取模 while(top0 nums[stk[top]]nums[i%numsSize]){ ans[stk[top]] nums[i%numsSize]; top--; } stk[top] i%numsSize; } *returnSize numsSize; return ans; }例题42 - 接雨水hard给定n个非负整数表示每个宽度为1的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。单增栈横向观察凹槽填雨水--由于使用单增栈当前元素大于栈顶元素时进行计算操作又因为次栈顶元素大于栈顶元素横向形成凹槽故重点在于记录当前元素栈顶元素和次栈顶元素heightmin(当前元素次栈顶元素)-栈顶元素widthright-left-1height0时sumheight*width#define MIN(a, b)((a)(b)?(a):(b)) int trap(int* height, int heightSize) { int* stk calloc(heightSize, sizeof(int)); int sum 0; stk[0] 0; int top 0; for(int i 1; iheightSize; i){ while(top height[stk[top]]height[i]){ // 由于要得到次栈顶,故top0 int mid stk[top],left stk[top-1], right i; int h MIN(height[left], height[right])-height[mid]; int w right-left-1; if(h0)sum h*w; // 有凹陷 top--; } stk[top] i; } free(stk); return sum; }例题84 - 柱状图中最大矩阵hard给定n个非负整数用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为 1 。求在该柱状图中能够勾勒出来的矩形的最大面积。单减栈做法和上一题42类似每个索引对应长度横向扩展成矩形由于求最大面积那么就是找下一个较小元素问题记录当前面积更新同样需要记录left, mid, right// 暴力思路--找到当前位置元素左边和右边第一个比他小的记录h与w更新ans // 超时91/99 int largestRectangleArea(int* heights, int heightsSize) { int ans 0; for(int i 0; iheightsSize; i){ int h heights[i], left -1, right heightsSize; for(int l i-1; l0; l--){ if(heights[l]h){ left l; break; } } for(int r i1; rheightsSize; r){ if(heights[r]h){ right r; break; } } int w right-left-1; ans fmax(ans, h*w); } return ans; } // 根据暴力思路利用单调栈 // 栈底-栈顶为递增那么自然次栈顶元素栈顶元素即左边第一个比他小的 // 然后遍历过程中遇到i比栈顶小即右边第一个比栈顶元素小的 #define MAX(a,b)((a)(b)?(a):(b)) int largestRectangleArea(int* heights, int heightsSize) { int* h malloc(sizeof(int)*(heightsSize2)); h[0] h[heightsSize1] 0; memcpy(h1, heights, sizeof(int)*heightsSize); int area 0; int* stk calloc(heightsSize2, sizeof(int)); stk[0] 0; int top 0; for(int i 1; iheightsSize2; i){ while(top h[i]h[stk[top]]){ int mid stk[top--]; int left stk[top], right i; int a h[mid]; int b right-left-1; area MAX(area, a*b); } stk[top] i; } return area; }