496. 下一个更大元素 I/503. 下一个更大元素 II/739. 每日温度

2020-05-10

1.题目描述

下一个更大元素

2.题解

1.直接进行暴力搜索 2.既然题目的标签是栈，就应该用到栈先进后出的特性，参考了官方的题解之后，我认为最能体现这种 特性的就是要找到下一个比当前元素值大的值。

3.代码

class Solution { public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {int l1=nums1.size(),l2=nums2.size();vector<int> res;for (int i=0;i<l1;i++){int r=0;for (int j=l2-1;j>=0;j--){if (nums2[j]>nums1[i]){r=j;}if (nums2[j]==nums1[i]){if (r==0) res.push_back(-1);else res.push_back(nums2[r]);}}}return res;} }; class Solution { public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {int l1=nums1.size(),l2=nums2.size();map<int,int>mymap;stack<int>mystack;vector<int>myvector;if (l2==0) return myvector; // 如果当前num2数组为空的话mystack.push(nums2[0]);for (int i=1;i<l2;i++){while (!mystack.empty()&&nums2[i]>mystack.top()){ // 栈不为空且当前元素大于栈顶元素mymap[mystack.top()]=nums2[i];mystack.pop();}mystack.push(nums2[i]);}while(!mystack.empty()){ // 如何栈中还有元素的话mymap[mystack.top()]=-1;mystack.pop();}for (int i=0;i<l1;i++){myvector.push_back(mymap[nums1[i]]);}return myvector;} };

503

和I的区别就是数组是循环数组，为了解决这一问题，我把nums数组复制两遍到nums2数组里面。 class Solution { public:vector<int> nextGreaterElements(vector<int>& nums) {int l=nums.size();vector<int> res;if (l==0) return res; // 如果nums数组为空vector<int> nums2;for (int i=0;i<l;i++) nums2.push_back(nums[i]);for (int i=0;i<l;i++) nums2.push_back(nums[i]); // 循环数组map<int,int> mymap;stack<int> mystack;for (int i=0;i<2*l;i++){while(!mystack.empty()&&nums2[mystack.top()]<nums2[i]){mymap[mystack.top()]=i;mystack.pop();}mystack.push(i);}while(!mystack.empty()){mymap[mystack.top()]=-1;mystack.pop();}for (int i=0;i<l;i++) {if (mymap[i]!=-1) res.push_back(nums2[mymap[i]]);else res.push_back(-1);}return res;} };

739

按照题目意思找到下一个比当前元素大的即可 class Solution { public:vector<int> dailyTemperatures(vector<int>& T) {int l=T.size();map<int,int>mymap;stack<int>mystack;vector<int>myvector;if (l==0) return myvector; // 如果当前数组为空的话for (int i=0;i<l;i++){while (!mystack.empty()&&T[i]>T[mystack.top()]){ // 栈不为空且当前元素大于栈顶mymap[mystack.top()]=i-mystack.top();mystack.pop();}mystack.push(i);}while(!mystack.empty()){ // 如何栈中还有元素的话mymap[mystack.top()]=0;mystack.pop();}for (int i=0;i<l;i++){myvector.push_back(mymap[i]);}return myvector;} };

总结

以上是生活随笔为你收集整理的496. 下一个更大元素 I/503. 下一个更大元素 II/739. 每日温度的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。