哪些网站设计好,一键部署wordpress,山东网站备案 论坛,上海市建设工程检测网739. 每日温度
给定一个整数数组 temperatures #xff0c;表示每天的温度#xff0c;返回一个数组 answer #xff0c;其中 answer[i] 是指对于第 i 天#xff0c;下一个更高温度出现在几天后。如果气温在这之后都不会升高#xff0c;请在该位置用 0 来代替。 示例 1:
…739. 每日温度
给定一个整数数组 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]
思路 /* 定义一个栈和数组result 单调栈首先存入数组的第一个下标然后从第二个元素开始遍历数组判断接下来遍历的元素和栈顶元素的关系 如果接下来遍历的元素小于或者等于栈顶元素则把该元素存入栈 如果接下来遍历的元素大于栈顶元素记录栈顶元素下标下的下标差这是我们要求的。 把栈顶元素弹出此时我们需要一个while循环进行对该元素和栈顶元素的比较和上述过程一样。 */
代码
class Solution {
public:vectorint dailyTemperatures(vectorint temperatures) {/*定义一个栈和数组result单调栈首先存入数组的第一个下标然后从第二个元素开始遍历数组判断接下来遍历的元素和栈顶元素的关系如果接下来遍历的元素小于或者等于栈顶元素则把该元素存入栈如果接下来遍历的元素大于栈顶元素记录栈顶元素下标下的下标差这是我们要求的。把栈顶元素弹出此时我们需要一个while循环进行对该元素和栈顶元素的比较和上述过程一样。*/vectorintresult(temperatures.size(),0);stackintst;st.push(0);for(int i 1;itemperatures.size();i){if(temperatures[i]temperatures[st.top()]){st.push(i);}else 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;}
};
496. 下一个更大元素 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] 是如上所述的 下一个更大元素 。 示例 1
输入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 。
示例 2
输入nums1 [2,4], nums2 [1,2,3,4].
输出[3,-1]
解释nums1 中每个值的下一个更大元素如下所述
- 2 用加粗斜体标识nums2 [1,2,3,4]。下一个更大元素是 3 。
- 4 用加粗斜体标识nums2 [1,2,3,4]。不存在下一个更大元素所以答案是 -1 。代码
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; // 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 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;}
};
还有很多瑕疵还需继续坚持
