leetcode 下一个更大的数（哈希表、单调栈）

一、LeetCode 496 下一个更大的数I
题目描述：
给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。

请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

思路：
暴力法+哈希表

代码如下：

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int>res;unordered_map<int,int>mp;for(int i=0;i<nums2.size();i++){if(i==nums2.size()-1){mp[nums2[i]]=-1;}else{int j=i+1;for(;j<nums2.size();j++){if(nums2[j]>nums2[i]){mp[nums2[i]]=nums2[j];break;}}if(j==nums2.size()){mp[nums2[i]]=-1;}}}for(int num:nums1){res.push_back(mp[num]);}return res;}
};

二、LeetCode 503 下一个更大的数II
题目描述：
给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

思路：
首先将原来的数组变为两倍的数
然后利用单调栈，查找最近的比它大的数

代码如下：

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {int n=nums.size();vector<int>res(n,-1);stack<int>stk;for(int i=0;i<n;i++){nums.push_back(nums[i]);}for(int i=0;i<2*n;i++){while(!stk.empty()&&nums[i]>nums[stk.top()]){int temp=stk.top();stk.pop();if(temp<n){res[temp]=nums[i];}}stk.push(i);}return res;}
};

三、LeetCode 31 下一个排列
题目描述：
实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须 原地 修改，只允许使用额外常数空间。

思路：
参考此处
1、从右向左找到第一个升序nums[i]>nums[j],
nums[i] 就是需要交换的小数（j 右边的肯定都是降序）
2、还是从右向左找到第一个大于 nums[i] 的数nums[k] 作为需要交换的大树
3、交换 nums[i] 和 nums[k]
4、i+1右边肯定是降序，反转变成升序
5、如果第一步找不到，则说明都是降序，直接第四步，所有的变成的升序

代码如下：

class Solution {
public:void nextPermutation(vector<int>& nums) {int left=0;int right=0;int i=nums.size()-2;for(;i>=0;i--){if(nums[i]<nums[i+1]){left=i;break;}}if(i<0){reverse(nums.begin(),nums.end());}else{for(int j=nums.size()-1;j>=0;j--){if(nums[j]>nums[left]){right=j;break;}}swap(nums[left],nums[right]);reverse(nums.begin()+left+1,nums.end());}}
};

四、LeetCode 556 下一个更大的数III
题目描述：
给你一个正整数 n ，请你找出符合条件的最小整数，其由重新排列 n 中存在的每位数字组成，并且其值大于 n 。如果不存在这样的正整数，则返回 -1 。

注意 ，返回的整数应当是一个 32 位整数 ，如果存在满足题意的答案，但不是 32 位整数 ，同样返回 -1 。

思路：
思路与上面的下一个排列一样

代码如下：

class Solution {
public:int nextGreaterElement(int n) {string nums=to_string(n);string cmp=to_string(INT_MAX);int left=0;int right=0;int i=nums.size()-2;for(;i>=0;i--){if(nums[i]<nums[i+1]){left=i;break;}}if(i<0){return -1;}for(int j=nums.size()-1;j>=0;j--){if(nums[j]>nums[left]){right=j;break;}}swap(nums[left],nums[right]);reverse(nums.begin()+left+1,nums.end());if(stod(nums)-stod(cmp)>0) return -1;return stoi(nums);}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！