LeetCode:Next Greater Element I(#496)

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;
}
不介意的话,可以请我喝杯咖啡吗?或扫一扫支付宝领红包