网站建设全程揭秘光盘文件,天津网站建设 seo,58创业网,拼多多网站目录
1. 单调栈的定义
2. 单调栈的常见用途
3. 案例分析
3.1 暴力解法 3.2 单调栈 4. 单调栈总结 1. 单调栈的定义
单调栈顾名思义#xff0c;就是栈内的元素是单调的。根据栈内元素的单调性的不同#xff0c;可以分为#xff1a;
单调递增栈#xff1a;栈内元素是单…目录
1. 单调栈的定义
2. 单调栈的常见用途
3. 案例分析
3.1 暴力解法 3.2 单调栈 4. 单调栈总结 1. 单调栈的定义
单调栈顾名思义就是栈内的元素是单调的。根据栈内元素的单调性的不同可以分为
单调递增栈栈内元素是单调递增的栈。
单调递减栈栈内元素是单调递减的栈。
2. 单调栈的常见用途
单调栈的用途给定一个序列指定一个序列中的元素求解该元素 左侧/右侧 第一个比自身 小/大的元素。
这便是单调栈的常见用途。下面结合具体的例子来理解单调栈哈N
3. 案例分析 原题链接 496. 下一个更大元素 I - 力扣LeetCodehttps://leetcode.cn/problems/next-greater-element-i/ 题目描述 nums1 中数字 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] 是如上所述的 下一个更大元素 。 3.1 暴力解法
暴力解法的思路就比较简单了。我们先初始化一个数组 ret用他的下标表示 nums2 中的每一个元素对应下标的值表示右侧第一个比它大的元素。然后从后往前(从前向后也行的)遍历 nums2 数组中的元素遍历每一个元素时向后找比该元素更大的数如果找到则将对应的结果保存到 下标为遍历元素的位置处如果没有找到的话就将 -1 保存到下标为遍历元素的位置处。 得到了 nums2 数组中每个元素的右边第一个比自身大的元素后只需要遍历一次 nums1 数组在 ret 数组中找到结果就行啦
假设 nums2 数组的大小为 N在求 nums2 数组中的每一个元素右侧第一个比自身大的数时时间复杂度是一个等差数列的求和即 O(N*N) 。在遍历 nums1 数组时因为 nums1 数组中的元素是nums2 数组中元素的子集遍历 nums1 的时间复杂度为 O(N)所以总的时间复杂度为O(N^2)。
int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize)
{int ret[10010];int j;for(int i nums2Size - 1; i0;i--){for(j i 1; j nums2Size; j){if(nums2[j] nums2[i]){ret[nums2[i]] nums2[j];break;}}if(j nums2Size){ret[nums2[i]] -1;}}*returnSize nums1Size;int* array (int*)malloc(sizeof(int)*nums1Size);for(int i 0;inums1Size;i){array[i] ret[nums1[i]];}return array;
}3.2 单调栈
单调栈的应用思路和双指针算法大体思路是一致的。先分析暴力解法怎么做然后分析具体题目找到其中隐藏的性质从而达到优化时间效率的目的。
emm怎么分析的就不说了后面会总结的。经过分析该问题发现在向右找比自身大的元素时哪些下标更大的但是值却更小的元素是不可能作为结果输出到 ret 数组的。 分析到这里我们就可以用单调栈为啥呢找的是右侧第一个比自身大的元素第一这两个字很能说明问题来解决问题了我们这里使用的是用数组模拟的栈哈效率比STL更高一点。向右找比自身大元素时需要从后往前遍历 nums2 数组。
我们还是以上面的 3 4 7 2 5 来举例分析开始遍历到 5 这个元素此时栈为空那就表明 5 这个元素右侧没有比自身大的元素(这里也能够说明为啥向右找需要从后往前遍历)将结果保存到 ret 数组。然后将 5 压入栈中。遍历到 2 时发现 2 小于栈顶的元素 5表明 2 这个元素右侧第一个比自身大的元素是 5将结果保存到 ret 数组中。遍历到 7 时发现 7 大于栈顶的元素 2这就是我们刚才说的2 是不可能作为结果输出的所以需要将栈顶的 2 弹出。弹出之后栈顶的元素就是 5 啦同样 小于 7但下标大于 7 的下标需要再次弹出。此时我们发现栈里面已经没有元素了说明 7 的右侧没有比自身大的元素 返回 -1。然后将 7 压入栈中。其他的元素就同理啦 同样假设 nums2 数组的大小为 N我们经过分析不难发现nums2 中的元素 最多被 压栈一次弹栈一次所以找 nums2 数组中 右侧第一个 比自身大的数的时间复杂度为 O(N)遍历nums1数组输出结果时也是 O(N)因此总的时间复杂度就是 O(N)。
int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){int stack[nums2Size 1], top 0;int ret[10010];for(int i nums2Size - 1; i 0; i--){while(top nums2[i] stack[top]){top--;}if(top){ret[nums2[i]] stack[top];}else{ret[nums2[i]] -1;}stack[top] nums2[i];}int* array (int*)malloc(sizeof(int)*nums1Size);for(int i 0;inums1Size;i){array[i] ret[nums1[i]];}*returnSize nums1Size;return array;
} 4. 单调栈总结 单调栈的常见用途就是这个啦显然是有四种情况的 1向左找第一个比自身大的数。 2向左找第一个比自身小的数。 3向右找第一个比自身大的数。 4向右找第一个比自身小的数。 通过以上的解题我们可能会有以下问题 1从前往后遍历还是从后往前遍历 答向右找数从后往前遍历向左找数从前往后遍历。 2弹栈的条件之一是大于等于还是小于等于 答找比自身大的数是大于等于正在遍历的数找比自身小的数是小于等于正在遍历的数。
