本文主要是介绍代码随想录算法训练营第五十八天|739. 每日温度、496.下一个更大元素I,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 1.每日温度
- 2.下一个更大元素I
1.每日温度
给定一个整数数组 temperatures
,表示每天的温度,返回一个数组 answer
,其中 answer[i]
是指对于第 i
天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0
来代替。
-
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0] -
示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0] -
示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]
提示:
1 <= temperatures.length <= 10^5
30 <= temperatures[i] <= 100
单调栈解法,用于一维数组寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置,本质是空间换时间。
求一个元素右边第一个更大元素,那就是从栈头到栈底递增,反之亦然。
具体操作流程如下: 通过遍历数组,将数组元素按照遍历规则压入栈(栈中元素就是待寻找下一个最大值
的元素),保证栈头到栈底递增。这样在每一次遍历元素跟栈头元素比较的时候,就能找到栈头元素的下一个最大值了
。
遍历规则就是遍历元素比栈头元素大,说明找到下一个最大值
,此时弹出栈记录与最大值距离。直到遍历元素比栈头元素小,此时压入当前遍历元素到栈头。
代码如下:
class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {stack<int> st;//单调栈vector<int> result(temperatures.size(), 0);//存放结果st.push(0);//第一个标号压入栈,栈中只存放元素标号for (int i = 1; i < temperatures.size(); i++) {if (temperatures[i] <= temperatures[st.top()]) {//小于等于栈顶元素可以压入栈,保证从栈头到栈底递增st.push(i);}else {while (!st.empty() && temperatures[i] > temperatures[st.top()]) {//遇到大于栈头元素,开始计算元素距离result[st.top()] = i - st.top();st.pop();}st.push(i);}}return result;}
};
时间复杂度:O(n)
空间复杂度:O(n)
2.下一个更大元素I
给定两个没有重复元素的数组 nums1
和 nums2
,其中 nums1
是 nums2
的子集。找到 nums1
中每个元素在 nums2
中的下一个比其大的值。
nums1
中数字 x
的下一个更大元素是指 x
在 nums2
中对应位置右侧的第一个比 x
大的元素。
返回一个数组 ans
,其中 ans[i]
表示按 nums1
索引顺序排列的每个数字的下一个更大元素。如果不存在,则对应位置输出 -1
。
-
示例 1:
输入:nums1 = [4,1,2], nums2 = [1,3,4,2].
输出:[-1,3,-1]
解释:- 对于
nums1
中的数字4
,nums2
中其右侧没有比它更大的数字,因此输出-1
。 - 对于
nums1
中的数字1
,nums2
中数字1
右侧的下一个较大数字是3
。 - 对于
nums1
中的数字2
,nums2
中其右侧没有比它更大的数字,因此输出-1
。
- 对于
-
示例 2:
输入:nums1 = [2,4], nums2 = [1,2,3,4].
输出:[3,-1]
解释:- 对于
nums1
中的数字2
,nums2
中数字2
右侧的下一个较大数字是3
。 - 对于
nums1
中的数字4
,nums2
中其右侧没有比它更大的数字,因此输出-1
。
- 对于
提示:
1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 104
nums1
和nums2
中所有整数互不相同nums1
中的所有整数同样出现在nums2
中
进阶: 你可以设计一个时间复杂度为 O(nums1.length + nums2.length)
的解决方案吗?
我们先找到nums2中每一个
下一个比其大的值
,然后判断是否存在于nums1。
找下一个比其大的值
使用单调栈方法
class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {stack<int> st;vector<int> result(nums1.size(), -1);if (nums1.size() == 0) return result;unordered_map<int, int> umap; // key:下标元素,value:下标for (int i = 0; i < nums1.size(); i++) {umap[nums1[i]] = i;}st.push(0);for (int i = 1; i < nums2.size(); i++) {if (nums2[i] <= nums2[st.top()]) { // 情况一st.push(i);} else { // 情况三while (!st.empty() && nums2[i] > nums2[st.top()]) {if (umap.count(nums2[st.top()]) > 0) { // 看map里是否存在这个元素int index = umap[nums2[st.top()]]; // 根据map找到nums2[st.top()] 在 nums1中的下标result[index] = nums2[i];}st.pop();}st.push(i);}}return result;}
};
这篇关于代码随想录算法训练营第五十八天|739. 每日温度、496.下一个更大元素I的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!