做网站需不需要云数据库,政务公开和网站建设工作问题,郑州网站建设hndream,西安小型企业网站建设739 每日温度
题目链接#xff1a;739.每日温度
给定一个整数数组 temperatures #xff0c;表示每天的温度#xff0c;返回一个数组 answer #xff0c;其中 answer[i] 是指对于第 i 天#xff0c;下一个更高温度出现在几天后。如果气温在这之后都不会升高#xff0c;…739 每日温度
题目链接739.每日温度
给定一个整数数组 temperatures 表示每天的温度返回一个数组 answer 其中 answer[i] 是指对于第 i 天下一个更高温度出现在几天后。如果气温在这之后都不会升高请在该位置用 0 来代替。
输入: temperatures [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]思路本题为单调栈的经典习题递减栈区分递增还是递减可以模拟执行看什么时候需要放数据因此当前温度高于栈顶时可给result赋值。
class Solution {
public:vectorint dailyTemperatures(vectorint temperatures) {stackint s;vectorint result(temperatures.size(), 0);for(int i 0; i temperatures.size(); i){while(!s.empty() temperatures[s.top()] temperatures[i]){result[s.top()] i - s.top();s.pop();}s.push(i);}return result;}
};496 下一个更大元素Ⅰ
题目链接496.下一个更大元素Ⅰ
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] 是如上所述的 下一个更大元素 。
输入nums1 [4,1,2], nums2 [1,3,4,2].
输出[-1,3,-1]
解释nums1 中每个值的下一个更大元素如下所述
- 4 用加粗斜体标识nums2 [1,3,4,2]。不存在下一个更大元素所以答案是 -1 。
- 1 用加粗斜体标识nums2 [1,3,4,2]。下一个更大元素是 3 。
- 2 用加粗斜体标识nums2 [1,3,4,2]。不存在下一个更大元素所以答案是 -1 。思路本题在上一题的基础上多使用一个map来记录元素与对应的下标关系。使用map记录nums1中(nums[i],i)的关系。result数组设置为nums1的大小。遍历nums2数组与上一题相同本题仅在nums2中找到对应的nums1的元素才记录答案。
class Solution {
public:vectorint nextGreaterElement(vectorint nums1, vectorint nums2) {stackint st;vectorint result(nums1.size(), -1);if (nums1.size() 0) return result;unordered_mapint, int umap;for (int i 0; i nums1.size(); i) {umap[nums1[i]] i;}for(int i 0; i nums2.size(); i){while(!st.empty() nums2[st.top()] nums2[i]){if (umap.count(nums2[st.top()]) 0){int index umap[nums2[st.top()]];result[index] nums2[i];}st.pop();}st.push(i);}return result;}
};
