Next Greater Element I(#496)
编号 | 名称 | 等级 |
---|
496 | Next Greater Element I | Easy |
思路
刚刚开始的思路是在第二个数组中寻找第一个数组的元素,如果找到并且后面还有比他大的就返回那个大数,否则就返回 -1 。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public class Solution {
public int[] nextGreaterElement(int[] findNums, int[] nums) {
int[] out = new int[findNums.length];
for (int i = 0; i < findNums.length; i++) {
for (int j = 0; j < nums.length; j++) {
if (findNums[i] == nums[j]) {
for (int k = 1; k < nums.length - j; k++) {
if (j + 1 < nums.length && findNums[i] < nums[j + k]) {
out[i] = nums[j + k];
findNums[i] = 0;
break;
}
}
if (findNums[i] != 0) {
out[i] = -1;
break;
}
}
}
}
return out;
}
}
|
这个代码在前面的测试数据可以过去,但是当测试数据到了后面的数的时候就 gg 了。

然后又又又看大神的代码。
通过 Stack 和 Map 进行操作。
代码
1
2
3
4
5
6
7
8
9
10
11
12
| public int[] nextGreaterElement(int[] findNums, int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
Stack<Integer> stack = new Stack<>();
for (int num : nums) {
while (!stack.isEmpty() && stack.peek() < num)
map.put(stack.pop(), num);
stack.push(num);
}
for (int i = 0; i < findNums.length; i++)
findNums[i] = map.getOrDefault(findNums[i], -1);
return findNums;
}
|