代码随想录训练营第五十八天|739. 每日温度、496.下一个更大元素 I

739. 每日温度

题目链接/文章讲解/代码讲解：代码随想录

1.代码展示

//739.每日温度
vector<int> dailyTemperatures(vector<int>& temperatures) {
	stack<int> st;
	vector<int> vnResult(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()]) {
				vnResult[st.top()] = i - st.top();
				st.pop();
			}
			st.push(i);
		}
	}
	return vnResult;
}

2.本题小节

        思考：首先明确单调栈的使用场景，通常是用在寻找任意一个元素的左边或者右边的第一个比自己小或者大的元素，本题是找比当前元素大的右边的第一个元素，并计算下标距离。单调栈的本质是牺牲空间来换取时间，所以时间复杂度为O(n)，只需要遍历一次即可，注意栈中储存的是下标，方便进行距离的统计。

        基本思路：首先创建容器和栈，分别用来储存结果和遍历过程中的元素，在遍历前先将下标0push到栈中，便于遍历中进行比较；对温度进行遍历，每次和栈顶的元素进行比较，小于等于时，说明当前元素不满足要求，将下标push到栈内；大于的话，则将栈顶对应下标位置与当前下标位置求差，计算的结果保存，这里主要要一直判断是否大于，因为当前元素不止比栈顶的大，计，注意把计算后的下标从栈内pop处，等到所有计算完毕后，将当前下标push到栈中。 

496.下一个更大元素 I  

 题目链接/文章讲解/代码讲解：代码随想录

1.代码展示

//496.下一个更大元素Ⅰ
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
	stack<int> st;
	vector<int> vnResult(nums1.size(), -1);
	if (nums1.size() == 0) return vnResult;
	unordered_map<int, int> nnMap;
	for (int i = 0; i < nums1.size(); i++) {
		nnMap.insert(make_pair(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 (nnMap.count(nums2[st.top()])) {
					int index = nnMap[nums2[st.top()]];
					vnResult[index] = nums2[i];
				}
				st.pop();
			}
			st.push(i);
		}
	}
	return vnResult;
 
}

2.本题小节

        思考：本题与上一题类似，与上一题不同的是，本题相当于求解的是在nums2出现的比nums1元素大的第一个右边的元素，因此在遍历nums2时出现了比栈顶大的元素时，判断栈顶的元素是否出现在nums1中，如果出现在，则填充当前下标对应的元素到栈顶元素对应下标的结果中。

        基本思路：首先要构建map，存入nums1下标对应的元素和下标，vector容器初始化时都为-1，剩余步骤和上一题相似。