网站安全建设目标,请你设计一个网络营销方案,磁力搜索器,安徽宿州住房与建设网站目录为什么单调栈的时间复杂度是O(n)496. 下一个更大元素 I方法一#xff1a;暴力方法二:单调栈哈希表739. 每日温度单调栈模版解优化503. 下一个更大元素 II单调栈循环遍历为什么单调栈的时间复杂度是O(n)
尽管for 循环里面还有while 循环#xff0c;但是里面的while最多执… 目录为什么单调栈的时间复杂度是O(n)496. 下一个更大元素 I方法一暴力方法二:单调栈哈希表739. 每日温度单调栈模版解优化503. 下一个更大元素 II单调栈循环遍历 为什么单调栈的时间复杂度是O(n)
尽管for 循环里面还有while 循环但是里面的while最多执行n次所以最大执行2n次即时间复杂度为O(n)。 不能只看有几层循环因为很多情况下内循环是不执行的可以这样理解n个元素每个元素最多进栈一次出栈一次所以是n
496. 下一个更大元素 I
https://leetcode-cn.com/problems/next-greater-element-i/ 给定两个 没有重复元素 的数组 nums1 和 nums2 其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在对应位置输出 -1 。
示例 1: 输入: nums1 [4,1,2], nums2 [1,3,4,2]. 输出: [-1,3,-1] 解释: 对于num1中的数字4你无法在第二个数组中找到下一个更大的数字因此输出 -1。 对于num1中的数字1第二个数组中数字1右边的下一个较大数字是 3。 对于num1中的数字2第二个数组中没有下一个更大的数字因此输出 -1。 示例 2: 输入: nums1 [2,4], nums2 [1,2,3,4]. 输出: [3,-1] 解释: 对于 num1 中的数字 2 第二个数组中的下一个较大数字是 3 。 对于 num1 中的数字 4 第二个数组中没有下一个更大的数字因此输出 -1 。 方法一暴力
先找到nums1的数在nums2对应的下标然后从那个下标开始向右遍历寻找是否存在。
class Solution {
public:int get_index(vectorint nums, int num){for(int i 0; i nums.size(); i){if(num nums[i]) return i;}return -1;} vectorint nextGreaterElement(vectorint nums1, vectorint nums2) {vectorint ans(nums1.size()); //答案数组stackint st;for(int i 0; i nums1.size(); i){//首先获取nums1[i](当前元素)在nums2数组中的下标int start get_index(nums2,nums1[i]);int flag 0;for(; start nums2.size(); start){if(nums2[start] nums1[i]){ans[i] nums2[start];flag 1;break; }}if(flag 0){ans[i] -1;}flag 0;}return ans;}
};方法二:单调栈哈希表
先忽略nums1因为nums1中元素在nums2中一定有。 对nums2进行单调栈处理需要记录的是一个键值对(该元素该元素右边第一个比该元素大的元素)。 这个是个典型的单调栈模型 需要注意在比较的过程如果满足st.back() nums2[i]就说明nums2[i]是大于栈顶元素的第一个元素(因为我们遍历是向右遍历的)。 经过这个过程后留在栈中的元素都符合没有找到右边元素大于该元素的条件所以应该返回-1。
class Solution {
public:vectorint nextGreaterElement(vectorint nums1, vectorint nums2) {vectorint ans(nums1.size()); //答案数组vectorint st;mapint,int hash_map;for(int i 0; i nums2.size(); i){while(!st.empty() st.back() nums2[i]){//说明第一个大于栈顶元素的元素为nums2[i]hash_map[st.back()] nums2[i];st.pop_back();}st.push_back(nums2[i]);}//如果此时栈中还有元素说明说明呢//说明栈中的元素在nums2数组中没有在右边找到比它还大的数所以需要赋值为-1while(!st.empty()){hash_map[st.back()] -1;st.pop_back();}//将哈希集合中的键值对转换为结果for(int i 0; i nums1.size(); i){ans[i] hash_map[nums1[i]];}return ans;}
};739. 每日温度
https://leetcode-cn.com/problems/daily-temperatures/ 请根据每日 气温 列表重新生成一个列表。对应位置的输出为要想观测到更高的气温至少需要等待的天数。如果气温在这之后都不会升高请在该位置用 0 来代替。
例如给定一个列表 temperatures [73, 74, 75, 71, 69, 72, 76, 73]你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度都是在 [30, 100] 范围内的整数。
单调栈模版解
一开始我使用了两个栈一个用来存该元素还有一个用来存该元素的下标用来计算相差天数时间复杂度会比较高也浪费了一些空间。后来发现了只使用一个栈存下标就行了。
class Solution {
public:vectorint dailyTemperatures(vectorint T) {vectorint ans(T.size()); //答案数组vectorint st_index;for(int i 0; i T.size(); i){while(!st_index.empty() T[st_index.back()] T[i]){//说明第一个大于栈顶元素的元素为nums2[i]ans[st_index.back()] (i - st_index.back());st_index.pop_back();}st_index.push_back(i);}//说明栈中的元素在nums2数组中没有在右边找到比它还大的数所以需要赋值为-1while(!st_index.empty()){ans[st_index.back()] 0;st_index.pop_back();}return ans;}
};优化
这一题还有KMP的解法等看到KMP的知识点再做贴个链接 https://leetcode-cn.com/problems/daily-temperatures/solution/mei-ri-wen-du-by-leetcode-solution/438101
503. 下一个更大元素 II
https://leetcode-cn.com/problems/next-greater-element-ii/ 给定一个循环数组最后一个元素的下一个元素是数组的第一个元素输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序这个数字之后的第一个比它更大的数这意味着你应该循环地搜索它的下一个更大的数。如果不存在则输出 -1。
示例 1: 输入: [1,2,1] 输出: [2,-1,2] 解释: 第一个 1 的下一个更大的数是 2 数字 2 找不到下一个更大的数 第二个 1 的下一个最大的数需要循环搜索结果也是 2。 单调栈循环遍历
原本next只能在当前元素的右边现在有可能出现在左边了。 我们可以在原数组后面再接一个原数组这样就可以完成这样的效果。 另外需要注意的是对于压栈的元素来说仍然只是需要压入前n个数不需要重复将后面链接的数组元素压入。 还需要注意的是 1、当前元素大于栈顶元素的时候才能进行出栈操作也就是说栈中的元素是严格单调递增的不允许出现等于的情况(这里可能出现重复的元素所以不能等于)
class Solution {
public:vectorint nextGreaterElements(vectorint nums) {int n nums.size();vectorint ans(n,-1); //答案数组vectorint st;for(int i 0; i 2 * n; i){while(!st.empty() nums[st.back()] nums[i%n]){ans[st.back()] nums[i%n];st.pop_back();}if(i n) st.push_back(i);}return ans;}
};
