目录

LeetCode:Next Greater Element I(#496)

youngxhui 收录于算法

2017-08-13 约 315 字预计阅读 1 分钟次阅读

目录

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;
    }