NextGreaterElementII2 [source code]


public class NextGreaterElementII2 {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < 2 * n; i++) {
            while (!stack.isEmpty() && nums[i % n] > nums[stack.peek()]) result[stack.pop()] = nums[i % n];
            if (i < n) stack.push(i);
        }
        return result;    
    }

    public static void main(String[] arg) {
        int[] input1 = {1,2,1};
        int[] input2 = {1,3,4,5,2};
        int[] input3 = {100,1,11,1,120,111,123,1,-1,-100};
        int[] input4 = {1,2,1,3,1,4,1,5,1,6};
        NextGreaterElementII2 tester = new NextGreaterElementII2();
        for (int i : tester.nextGreaterElements(input3)) System.out.println(i);
    }
}

这个算法最后的时间是49ms, 71%, 所以明显还是有很大的改进空间的. 看了一下solutions, 优秀的算法基本都是30ms 以下的;

这里首先要提到一个思考问题的思路,这个技术在前面那个暴力解的发现中也起到了作用,就是一个 reduction 的概念, 或者更准确的来说, 应该叫 relaxation: 一点一点的减少题目的条件,先找到一个简单问题的解,然后加上之前被ignore 的 constraint; 比如这里,可以先考虑这个要完成 circular 的问题,先考虑就是一个返回一个普通的 array 的问题. 或者假设先不存在 duplicate,这种毕竟往往也简单一些.
这个是一个值得训练的普遍性的思维模式,尤其在 CS 的问题当中很使用;

这里先大概解释一下之前那一题也没有解释清楚的一个遗留问题,就是 stack 到底是用来干什么的? 到底怎么理解它?
1.首先要知道的是,Stack 的核心就是,保存趋势. 而这两个next greater element其实做的都是一个寻找趋势断点的问题.
\ /\ /\
\ / \ / \
\/ \/ \/
用这样一个趋势来理解数字的变化趋势.
那么你比如找nums[1]的 NGE,其实找的就是什么时候,nums[1]所在的这个趋势中断了.上面那个不是很说明问题,看这个:
\
\ \
\ \ /
\ \/
看这个,就比较形象,这里nums[4]就是前面nums[0] - nums[3]所有的NGE,因为0-3都在同一个趋势里面;
而 Stack 所做的就是保存这种趋势,为什么这么说呢? 你可以这样考虑,假设我们这里用 Bag,不用 Stack,行不行?
为什么不行?因为首先你要知道你是怎么使用 Stack 的,你的 Stack 你使用的时候暴露给你的其实就只有一个 peek,那么你 peek 的这个 top 的数字,能够代表你里面的内容吗? 如果是 bag,假设给你一个 peek,那么其实一点用都没有,因为所有的elements 之间毫无关系,你就算看到 top 是个什么,也完全没有办法利用.
但是 stack 就不一样,比如上面这个例子,0-3全都在一个趋势,所以他们在放到 Stack 里面的时候,这个趋势也被放到了 Stack 里面,这个趋势就是 decreasing;而 NGE 问题找的目标,其实你好好理解,就是一个the breaking point of the current element's enclosing trend,所以用这个 Stack 来解决,简直是教科书的做法.

后面又重新思考了一下, 感觉 Stack 更多的时候做的工作就是类似于一个 buffer 的处理? 有一部分的东西, 知道要一起处理, 但是仅仅是扫描到比如 i 的位置的时候, 还不知道是否到了处理的时机, 只要先缓存起来;

至于 NGE1里面用到的那个 map,其实就是一个保存结果的作用. 这两个问题的核心,还是理解这个 stack.
事实上,NGE 问题里面 Stack 的用法还算是比较直接和初级的,可以预想到后面肯定有很多问题,对于 Stack 有更加晦涩的使用.

2.关于 NGE2和 NGE1的区别:
circular 这个问题其实很好解决,mod 和loop for 2*n这个其实我自己都想到了. 事实上, 把一个 array 拓展到两倍长度, 是处理circular array的一个常规办法;
这个问题的难点,是有 duplicate 了.
有 duplicate 带来的直接的和 NGE1的区别就是,你不能用 map 来保存结果了. 为什么?
首先你要理解 map 是什么? 按照我么 POPL 的理解,map 就是一个 heap,一个 store,一个内存;
就是用来让你保存 value 的;
那么 map 为什么这里就不行了? 因为 map 的 Key 只能是唯一的! 也就是对于一个 value (为了防止混淆,key/value 指代的是普通语境下的意思,Key/Value 指代的是 Map 的 attributes) ,这里就是说 Map 的一个 Key,你只能有一个结果.
这个在有 duplicate 的情况下是不行的,因为我们最后的结果是什么样的? think what kind of output you ultimately want.
我们最后的结果,一个 value 是可以有好几个不同的 NGE 的. 所以绝对不能按照 value 来保存结果.
NGE2按说是比 NGE1难的,但是实际上做起来用到的技术并没有体现这个观点. NGE1其实可以说是 NGE2的一个特殊情形.
NGE2实际上要解决的是更普遍的一个问题.
我们按照 value 来保存结果行不通,那么按照什么来保存结果? 可以举一个例子来思考,比如[1,2,1,3]这个,我们最后希望nums[0] and nums[2]这两个1是要有不同的结果的: 看出来了吗?
这两个1唯一有区别的是什么? 是 index. 所以我们最后保存结果就是按照 index 来保存就行了. 而要做到这个,肯定不能用 Map,因为 Map 针对的就是 value.我们直接用一个 Array 就行了.

另外, 这里要学习到的一个技术是, 举例子一定要从简单化开始, 比如, 一开始不要想那种一会儿上去一会儿下来的锯齿状的例子, 直接就找类似3,2,1,4这样的简单的例子;

3.理解了上面这两点之后,写 NGE2应该就不难了. 一个问题值得思考: 我们 Stack 里面保存的具体应该是什么? 是 nums里面的 index 还是 value? 答案应该是 index, 因为 index 在这里更具有唯一性.

4.从另外一个角度思考,我们这里完成的到底是什么? 我们把一个n^2的算法变成了2n的算法,这个转化的目的性,更前面,比如 2sum,的思考是一样的. 按说直观上必须n*n 才能做完的事情,你想要快到 n 就做完,你就必须做到一个preserve previous information的功能. 2sum 里面用一个 map 来做到, 这里用的是 Stack 来做到, 指导思想都是一样的,用数据结构来保存历史信息,但是细致划分有一定的差别:
2sum里面的这个 Map,做的是保存之前 element 的信息,来对当前 element 形成参考. 以前的那些element,过了就过了,不管了,我们需要的是利用他们完成对当前 element 的1-pass decision; 但是 NGE2这里的这个 Stack,做的其实类似一个 cache.当我们利用 Stack 找到了一个断点,Stack 里面的所有能够被这个断点 pop 出来的,我们全都 pop出来. 统一进行处理,大家只是处在一个等待区; 当然,从另一个角度来讲,其实也可以把2sum 的 map 理解为等待区,因为加法是要有两个参与者的,所以当你找到了operand2的时候,其实也意味着你找到了operand1.

5.最后一个问题,就是到底怎么刷算法题? 对于很多不算奇葩的问题,最好自己上来哪怕没有什么好的思路,直接先一个暴力解做出来, 就像我们做 NGE2的时候这样. 这样才算是刷题. 不要上来就想着去看答案. 虽然别人写的最优解非常聪明,但是抄是一点意义都没有的.
另外一个想到的问题就是后面尽量还是依靠电脑刷题,好于 pdf 刷题. 像这题,没有自己在电脑上跑一跑, 看看 stdout 的提示,估计理解起来要花很多的时间.
而且只有自己一个代码一个代码的敲,才能锻炼这种编程的肌肉记忆,就好像读书练口语一样. 不要有时候想一个loop header boundary 都要想半天,未免就丢人现眼了.

6.忘了提到一件事情,就是
!stack.isEmpty() && nums[i%n] > nums[stack.peek()]
这一行,这里其实原来的作者用了一个巧妙的 shortcircuiting,如果stack is empty,那么后面那部分直接就被 skip. 这个发生在最开始的第一个 iteration,如果不用这个技术的话,stack.peek()用在最开始的empty stack的时候直接就会报错;
这个技术后面不知道能不能学会,总结一下可以使用的场合,或者说可以针对的问题. 最起码的,这里这种针对data structure proper initialization的场合肯定是可以使用的;

Problem Description

Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element.
The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, output -1 for this number.

Example 1:
Input: [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2;
The number 2 can't find next greater number;
The second 1's next greater number needs to search circularly, which is also 2.
Note: The length of given array won't exceed 10000.

Subscribe to see which companies asked this question.

Hide Tags Stack
Hide Similar Problems (E) Next Greater Element I

LC556 NextGreaterElementII2

NextGreaterElementII2 [source code]

Problem Description

results matching ""

No results matching ""