记录生活中的点点滴滴

0%

下一个更大元素

写一下这一类题的求解过程:

496. 下一个更大元素 I

503. 下一个更大元素 II

31. 下一个排列

556. 下一个更大元素 III

496. 下一个更大元素 I

其实这题很直观,怎么做?用单调栈呗!

因为得到对应的值之后还需要遍历nums1,然后找到每一个对应的值,所以还需要一个map结构去存储。

基本思想就是这样,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
//利用单调栈来解决
//先遍历nums2,通过map存放对应元素和右边最大值
//然后遍历nums1,通过map获取对应元素的值
Stack<Integer> s = new Stack<>();
HashMap<Integer,Integer> map = new HashMap<>();
//倒着遍历nums2
for(int i=nums2.length-1;i>=0;i--){
while(!s.isEmpty() && s.peek()<nums2[i]){
s.pop();
}
if(!s.isEmpty()){
map.put(nums2[i],s.peek());
}
s.push(nums2[i]);
}
int n = nums1.length;
int[] res = new int[n];
for(int i=0;i<n;i++){
res[i] = map.getOrDefault(nums1[i],-1);
}
return res;
}

OK,下面看进阶版的:

503. 下一个更大元素 II

这题首先,我们可以确定,不用map结构了。但是却引入了一个难题,就是它是循环的!

怎么办?

其实很简单,就是把元素遍历两遍(通过设置i=2*n+1,然后区域得到下标),不就OK了!

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int[] nextGreaterElements(int[] nums) {
//环形的话,其实把nums2数组变成原来的二倍长度即可
int n = nums.length;
Stack<Integer> s = new Stack<>();
int[] res = new int[n];
for(int i=2*n-1;i>0;i--){
while(!s.isEmpty() && s.peek()<=nums[i%n]){
s.pop();
}
res[i%n] = s.isEmpty() ? -1 : s.peek();
s.push(nums[i%n]);
}
return res;
}

OK,它还有第三道题,但是做之前,先做一道热身题:

31. 下一个排列

找到下一个排列的数组!

首先明确一点,如果数组本来就是降序的,那么只能把数组反转了!

如果不是降序的话,怎么办?

其实就是从右边开始迭代往前找,找到一个比后一个小的,此时这个之后肯定是降序的 。比如 2 1 6 5 4,找到1,之后全都是降序的,其实就是把1之后的 6 5 4降序,变成 4 5 6 ,然后4再与1交换即可。注意交换的是,从4 5 6的第一位4开始遍历,遇到第一个比1大的就交换。

比如 2 3 6 5 4 1,找到 3<6,然后把 6 5 4 1 变成 1 4 5 6,然后从1开始遍历,找到第一个比3大的,就是4,然后3和4交换,得到 2 4 1 3 5 6,就是最终的结果!

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public void nextPermutation(int[] nums) {
int n = nums.length;
for(int i=n-1;i>0;i--){
if(nums[i]>nums[i-1]){
//找到时,i之后的肯定是降序的
Arrays.sort(nums,i,n);
//然后变成升序的,从前往后找到第一个比nums[i-1]大的,交换即可
for(int j=i;j<n;j++){
if(nums[j]>nums[i-1]){
int t = nums[j];
nums[j] = nums[i-1];
nums[i-1] = t;
return;
}
}
}
}
//如果执行到这一步说明:数组是降序数组
//下面的方法将数组变成升序的数组
int l=0,r=n-1;
while(l<=r){
int t = nums[l];
nums[l++] = nums[r];
nums[r--] = t;
}
}

这道题只要弄懂了之后,再看看下面的题,就应该差不多可以做出来了!

556. 下一个更大元素 III

看到没,不就是把一个数先拆成一个数组吗,然后找到它的下一个排列,然后再把这个数组转换成数就OK了嘛!

不过有一点要注意,就是可能int会溢出,所以转换的时候,要先用long类型去做,如果溢出了,直接返回-1即可,没溢出的话返回int类型的数就OK。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public int nextGreaterElement(int n) {
int len = 0, t = n;
//得到n的位数
while(t>0){
len++;
t/=10;
}
//根据n得到数组,例如123则得到数组[1,2,3]
int[] arr = new int[len];
t=n;
boolean flag = true;//看看是否是递减序列
for(int i=len-1;i>=0;i--){
arr[i] = t%10;
t/=10;
if(i<len-1 && arr[i]<arr[i+1]){
flag = false;
}
}
//如果是递减数组,则直接返回-1
if(flag)return -1;
//不是递减序列,则参考 下一个排列 https://leetcode-cn.com/problems/next-permutation/
//参考这道题的做法,得到下一个排列数组,再利用getRes函数得到返回的结果
for(int i=len-1;i>0;i--){
if(arr[i]>arr[i-1]){
//找到时,i之后的肯定是降序的
Arrays.sort(arr,i,len);
//然后变成升序的,从前往后找到第一个比nums[i-1]大的,交换即可
for(int j=i;i<len;j++){
if(arr[i-1]<arr[j]){
int temp = arr[i-1];
arr[i-1] = arr[j];
arr[j] = temp;
return getRes(arr);
}
}
return getRes(arr);
}
}
return -1;
}
//根据数组得到数,例如[1,2,3]返回123。。要先设置成long类型,如果溢出,则返回-1即可!
public int getRes(int[] arr){
int n = arr.length;
long sum = 0;
for(int i=0;i<n;i++){
sum = sum*10+arr[i];
}
return sum>Integer.MAX_VALUE ? -1 : (int)sum;
}