NextGreaterElementI [source code]

public class NextGreaterElementI {
    public int[] nextGreaterElement(int[] findNums, int[] nums) {
        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);          // exhaustive conditional case handling
            stack.push(i);       // this will happen no matter what
        }
        for (int i = 0; i < findNums.length; i++) findNums[i] = map.getOrDefault(findNums[i], -1);
        return findNums;
    }

    public static void main(String[] arg) {
        NextGreaterElementI tester = new NextGreaterElementI();
        int[] nums1 = {4,1,2,3,5};
        int[] nums2 = {1,3,4,9,2};
        // int[] nums1 = {4,1,2};
        // int[] nums2 = {1,2,3,4};
        for (int i : tester.nextGreaterElement(nums1, nums2)) System.out.println(i);
    }
}

这个题目刚开始没有理解对,以为是按照 position 查找,结果搞了半天提交了几个全都是报错,浪费了自己的成功率.
后来好半天才理解了题目的意思的next greater指的是大小. 但是想了半天还是不理解怎么做.
我们说过,一个问题,总是从简单总结开始,所以首先理解这个是一个什么问题,然后找一个最简单的方法,然后改进:
首先,这个问题是一个最典型的算法题,两个 collection (往往是两个 array) 作为 input;
然后具体到这个题目,是一个用一个 list 来查找另外一个 list 的问题.
那么最简单的做法是什么? 暴力搜就是了,findNums 里面每一个 int 拿出来,过一遍 nums,保留比这个 int 的最小值,这个很好做,最后时间复杂度O(nm).这个最简单的做法还是要想得到.
然后我们怎么升级? 一个比较可能的做法是把 nums 全部都 sort 一遍,这样用 findNums 的 key 来搜索的时候会更快一些.不过这个改进其实还是比较 trivial 的.

今天突然意识到我对这个问题的理解一直有问题,我们要找的,是比如 nums 是 1,3,4,2,那么你手上拿着2,找的其实是首先要确认2在nums 里面,否则就return -1;然后如果2在 nums 里面那么最后返回的就是2在 nums 里面后面的第一个比它大的数字.
这个题目的要求总体来说是比较奇怪的,不过介绍的算法确实是一个比较有启发性的.

另外这里最后一个要提到的地方是这一题后面直接在 findNums 里面做修改,相当于in place,这个一开始没有想到不要太过意不去,不是什么特别重要的问题.
刚开始就按照你自己的习惯,直接上来一个 result,我觉得是没有什么问题的.
不过慢慢要训练这种直接return in input的技术,算是一个可以加分的小噱头.
可以利用这个inplace return的技术的问题,往往有一个特点,类似这一题,就是你已经把关于 input 的完整信息都保存下来了(你需要的那一部分信息,像是这里的stack and map);
在这种问题当中,因为你其实已经相当于预支了你的 space budget,所以在最后 return 的时候小气一点点是很正常的;

这个算法最后的时间是12ms, 42%, 好像有点慢;

另外这个算法其实也是后来看的别人的答案. 这个是作者的解释:

Key observation:
Suppose we have a decreasing sequence followed by a greater number
For example [5, 4, 3, 2, 1, 6] then the greater number 6 is the next greater element for all previous numbers in the sequence

We use a stack to keep a decreasing sub-sequence, whenever we see a number x greater than stack.peek() we pop all elements less than x and for all the popped ones, their next greater element is x
For example [9, 8, 7, 3, 2, 1, 6]
The stack will first contain [9, 8, 7, 3, 2, 1] and then we see 6 which is greater than 1 so we pop 1 2 3 whose next greater element should be 6

就算是之前做过一遍, 现在回头来看还是有点不理解. stack 感觉目前来看还是我的弱项.
当然这个算法本身还是要先理解他的思路, 也就是这里这个key observation, 在这之后, 各种讨论代码才有意义. 实际上代码本身写的还是挺简洁的;

Problem Description

You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2.
Find all the next greater numbers for nums1's elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2.
If it does not exist, output -1 for this number.

Example 1:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
For number 1 in the first array, the next greater number for it in the second array is 3.
For number 2 in the first array, there is no next greater number for it in the second array, so output -1.
Example 2:
Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
For number 2 in the first array, the next greater number for it in the second array is 3.
For number 4 in the first array, there is no next greater number for it in the second array, so output -1.
Note:
All elements in nums1 and nums2 are unique.
The length of both nums1 and nums2 would not exceed 1000.

Hide Tags Stack
Hide Similar Problems (M) Next Greater Element II