-
Notifications
You must be signed in to change notification settings - Fork 6
/
_496_Next_Greater_Element_I.java
95 lines (83 loc) · 2.53 KB
/
_496_Next_Greater_Element_I.java
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
package leetcode;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
/**
* Created by pingcai on 17-5-2.
*
* 找出数组中每一元素右边大于它的数,没有置为-1
*
*/
public class _496_Next_Greater_Element_I {
public static void main(String[] args) {
System.out.println(Arrays.toString(new _496_Next_Greater_Element_I().nextGreaterElement(new int[]{4, 1, 2}, new int[]{1, 3, 4, 2})));
}
// 堆栈相结合
public int[] nextGreaterElement(int[] findNums, int[] nums) {
if (findNums == null || findNums.length <= 0) {
return findNums;
}
Map<Integer, Integer> map = new HashMap<>();
Stack<Integer> stack = new Stack();
for (int i : nums) {
while (!stack.empty() && stack.peek() < i) {
map.put(stack.pop(), i);
}
stack.push(i);
}
for (int i = 0; i < findNums.length; i++) {
//findNums[i] = map.getOrDefault(findNums[i], -1); //JDK 1.8
findNums[i] = map.get(findNums[i]) != null ? map.get(findNums[i]) : -1;
}
return findNums;
}
/*
//提前用 map保存nums的下标,则查找时间复杂度为O(1)
public int[] nextGreaterElement(int[] findNums, int[] nums) {
if (findNums == null || findNums.length <= 0) {
return findNums;
}
Map<Integer, Integer> map = new HashMap<>();
int q = 0;
for (int i : nums) {
map.put(i, q++);
}
for (int i = 0; i < findNums.length; i++) {
int start = map.get(findNums[i]);
int b = findNums[i];
findNums[i] = -1;
for (int j = start + 1; j < nums.length; j++) {
if (nums[j] > b) {
findNums[i] = nums[j];
break;
}
}
}
return findNums;
}
// 蛮力法
public int[] nextGreaterElement(int[] findNums, int[] nums) {
if(findNums == null || findNums.length <= 0){
return findNums;
}
int i = 0;
for(int x : findNums){
int b = find(nums,x);
findNums[i++] = b;
}
return findNums;
}
public int find(int[] nums,int i){
int max = -1;
for(int x = nums.length-1;x>0;x--){
if(nums[x]==i){
return max;
}
if(nums[x]>i){
max = nums[x];
}
}
return max;
}*/
}