Stack (Java) - ShuweiLeung/Thinking GitHub Wiki

1.（682:Easy）Baseball Game

• 该题就是简单的对堆顶前几个元素的操作，严格按照题意实现即可。

2.（496:Easy）（非常经典题）Next Greater Element I

• 该题用最暴力的解法应该可以通过OJ，但效率不高，且没有用到stack思想。
• 该题正确的高效解法是：我们用一个堆栈维护一个递减的序列，如[5, 4, 3, 2, 1, 6]，那么6就是该元素前的所有数字的next greater element，那么我用堆栈维护一个递减序列，当stack.peek()大于等于当前数组中的元素x时，将x压栈，否则将stack堆顶处所有元素出栈，那么这些被弹出元素的next greater element都是x。如堆栈中首先为[9, 8, 7, 3, 2, 1]，当我们遍历到数字6时，将3、2、1出栈，这三个元素的next greater element就是6，更新后的堆栈是[9,8,7,6]。按照该思路，我们先遍历nums2数组，用map存储每个元素的next greater element，之后再看nums1数组需要找出哪些元素的next greater element即可。具体思路看代码。

3.（232:Easy）Implement Queue using Stacks

• 该题只能使用堆最基本的操作来模拟队列的实现，对于peek操作及pop操作，我们需要一个辅助堆，将原来堆中的元素全部倒序装入辅助堆中即可获得或者删除堆底元素。

4.（225:Easy）Implement Stack using Queues

• 该题和上面第3题（232）思路一样，也需要一个临时队列作为中转。

5.（155:Easy）（非常非常经典题）Min Stack

• 该题一开始想到的就是优先队列Priority Queue，它能实现最小值的O(1)时间存取，但需要借用remove(Object)方法来删除，stack.pop()出的元素，严格来说不符合题目要求。
• 正常的思考过程是，我们用一个min变量在push时保存当前stack中最小的数值，但当pop时，若出栈数字等于min，那么我们需要更新min值，但此时我们没有之前比较的历史记录，因此，需要设立一个minStack来保存之前的历史最小值记录。具体思路是，用minStack保存到当前元素的最小值集合，在push时，只有x比minStack栈顶元素小时，才将x同时push进minStack，minStack维护的是一个"递减"数列。在出栈时，若stack.pop() != minStack.peek()，那么不对minStack进行处理，否则应同时将minStack出栈（stack.pop() = minStack.peek()）。
• 那么我们可能就会想到，如果stack.pop()的元素比minStack栈顶元素大,却比minStack栈底元素小,那么在pop出minStack的栈顶元素后,当前最小元素是否应为之前stack出栈的元素,这样便发生错误呢?其实不然，假如依次5，4，6，2，3入stack栈，minStack为5，4，2。在pop时，直接将3出栈，因为3 > 2，所以不对minStack进行操作。但我们会发现，此时并不会出现开始提到的问题，因为元素3是后入栈的，所以在它出栈时，并不会对之前已入栈元素的大小关系造成影响。具体实现参看代码。

6.（503:Medium）（非常经典题）Next Greater Element II

• 该题和第2题（496）的思路相近，都需要用到map和stack集合，区别在于：1. 该题nums数组中可能会出现重复元素，所以map的key应为nums中的下标索引，value为该位置的next greater element的值。 2. 该题nums数组是circular的，为一个环，因此我们应该循环遍历两遍nums数组，求解所有的next greater element。具体思路看代码。该思路优化：不用map集合，而改用长度为nums的数组作为map功能，应该更高效。（beat 22%）

该题应该还有其他更高效的方法，下次复习时参看discuss

7.（636:Medium）（非常经典题）Exclusive Time of Functions

• 根据题目中给的例子，我们可以看出来，当一个函数start了之后，并不需要必须有end，可以直接被另一个程序start的时候强行关闭。而且，在某个时间点上调用end时，也不需要前面非得调用start，可以直接在某个时间点来个end，这样也算执行了1秒，得+1秒（end是指在某一秒的末尾结束，那一秒也算该程序运行的时间）。且end与堆顶的function id一定是相等的，类似于括号匹配。具体实现看代码。

8.（341:Medium）（经典题）Flatten Nested List Iterator

• 该题给了NestedInteger的接口，不是让我们继承该接口来进行方法的重写实现，而是像一个"目录"一样，告诉我们该类有哪些方法我们可以直接调用。
• 该题主要是在构造方法初始化时，将传入的list进行递归的搜索，按搜索顺序存入一个全局的list成员变量中，之后设立一个全局成员指针i，当i<list.size()时，hasNext()返回true；调用next()方法，返回list.get(i)，并将i指针加1即可。

9.（394:Medium）（非常经典题）Decode String

• 该题其实就是字符串String类型的题目，之前总结过：这种"字符串中带括号"的解析问题，需要使用"递归"或者"堆栈"来解决，每遇到内层的一个括号，向下递归一次或压栈一次，当内层括号处理结束后，向上层返回递归结果或者出栈。个人感觉这种题使用递归应该较简单，但因为此题被标注为Stack题，所以我在这里使用堆栈尝试解决了一下。中心思想和总结的一样，具体实现参看代码及备注。
• 注意：只要出现'['']'左右括号，括号前的数字一定是大于1的
• 该题感觉用Stack实现的话代码还是比较冗余，用DFS实现代码看起来非常简洁。思路是，我们把一个中括号中的所有内容看做一个整体，一次递归函数返回一对中括号中解码后的字符串。给定的编码字符串实际上只有四种字符，数字，字母，左中括号，和右中括号。那么我们开始用一个变量i从0开始遍历到字符串的末尾，由于左中括号都是跟在数字后面，所以我们首先遇到的字符只能是数字或者字母，如果是字母，我们直接存入结果中，如果是数字，我们循环读入所有的数字，并正确转换，那么下一位非数字的字符一定是左中括号，我们指针右移跳过左中括号，对之后的内容调用递归函数求解，注意我们循环的停止条件是遍历到末尾和遇到右中括号，由于递归调用的函数返回了子中括号里解码后的字符串，而我们之前把次数也已经求出来了，那么循环添加到结果中即可。

    //DFS
    private int pos = 0;
    public String decodeString(String s) {
        StringBuilder sb = new StringBuilder();
        String num = "";
        for (int i = pos; i < s.length(); i++) {
            if (s.charAt(i) != '[' && s.charAt(i) != ']' && !Character.isDigit(s.charAt(i))) {
                sb.append(s.charAt(i));
            } else if (Character.isDigit(s.charAt(i))) {
                num += s.charAt(i);
            } else if (s.charAt(i) == '[') {
                pos = i + 1;
                String next = decodeString(s);
                for (int n = Integer.valueOf(num); n > 0; n--) sb.append(next);
                num = "";
                i = pos;
            } else if (s.charAt(i) == ']') {
                pos = i;
                return sb.toString();
            }
        }
        return sb.toString();
    }

该题自己的堆栈实现方法可能有些细节（压栈时条件）处理的逻辑不是很清晰，下次复习时可以参看discuss中的解法

<10>.（331:Medium）（非常经典题）Verify Preorder Serialization of a Binary Tree

• 该题Discuss中高票答案，也是非常聪明的解法，是根据结点的"入度"与"出度"来衡量输入序列是否合法的。因为一个非空结点可以引出两个箭头，而空结点只能消耗一个箭头而不产生新的箭头，所以据此可以实现一个out-in算法。
• 常规解法是，当我们遇到数字时压入栈中，当我们遇到"#"，需要判断当前栈顶是否为"#"，如果是的话，我们就需要把当前栈顶的"#"以及次栈顶数字n出栈，代表以次栈顶n为根节点的子树全部遍历完毕，然后再压入"#"到栈顶位置，代表该子树已遍历结束。按该规则直到整个序列都遍历完且栈中只有一个字符"#"时，代表序列是符合条件的，结束。如下图所示：（该思路可以在Eclipse中用debug模式详细运行一遍，从而便能了解该方法的具体原理）

      4                    4
     / \                  / \
   2(n) ...      =>      #  ...
  / \
 1   4

• 参考链接：Out-in解法思路过程演示

11.（735:Medium）（经典题）Asteroid Collision

• 就是简单的行星相撞的问题，如果行星不能相撞，则将行星入栈，否则与栈顶对比，只有方向相反且会相遇的行星才能相撞，若当前的行星比栈顶的行星质量大，则栈顶行星出栈，需要继续循环判断新栈顶行星是否还是会与当前行星相撞；若当前的行星比栈顶的行星质量小或相等，则当前行星灭亡或双亡，栈顶维持不变或栈顶出栈。若当前行星与栈顶行星方向相反，但背道而驰，则将当前行星加入栈顶；若当前行星与栈顶行星方向相同，则当前行星入栈。

自己的实现代码写的并不简洁，下次复习时可以参看discuss中的代码

12.（150:Medium）（经典题）Evaluate Reverse Polish Notation

• 该题其实就是逆波兰表达式（后缀表达式）的计算，借用堆栈即可。该题简单的地方在于，题目的输入已经将中缀表达式转化为了后缀表达式，所以比较容易。

13.（补）（844:Easy）Backspace String Compare

• 该题类似于word中文字编辑与删除的底层实现，借用堆栈stack即可。

<14>.（456:Medium）（非常非常经典题）132 Pattern

• 首先需要明确：i、j、k的下标索引并不一定是紧密相邻的，即不一定是i + 1 = k, k + 1 = j。
• 该题最容易想到的方法是brute-force暴力求解，利用三层嵌套for循环找出可能的i、j、k，但该法当然超时。
• 那么在暴力求解O(n^3)时间复杂度的基础上，我们可以进一步优化，思路是：我们会发现，如果固定j，那么我们只需要在j下标的左侧找一个比nums[j]小的数nums[i]，在nums[j]右侧找一个值在区间(nums[i], nums[j])之间的数即可得到答案，而在固定j的前提下，nums[i]越小，那么nums[j]落在上述区间范围内的可能性越大。而且在j从左向右遍历的同时，可以获得从[0,j-1]下标范围内的最小值信息。这样，我们就可以将brute-force解法中外层的两个for循环合并成一个，得到O(n^2)的解法。具体实现细节参看代码实现，但该方法效率仍然很低，只能beat 24%。因为我们每固定一个j，都需要重新扫描[j+1,len-1]的元素，我们可以利用之前扫描[j+1，len-1]的结果，为后续的i、j、k组合提供"有用"信息。从而使用空间-时间平衡策略，得到下面的O(n)时间复杂度、O(n)空间复杂度的解法。
• 参考链接：O(n^3)->O(n^2)->O(n)实现英文详解

该题O(n)时间复杂度、O(n)空间复杂度的解法思路比较复杂，第一次做的时候看过一次但不大理解，下次复习时需要再研究，并且和其他同学讨论

15.（402:Medium）（非常非常经典题）Remove K Digits

• 该题也被归为Greedy贪心算法类题目。该题其实主要关注的是删除的策略，我们从左向右扫描输入字符串并装入结果集中，如果当前扫描的字符比结果集最后一个数字小，那么就把结果集最后一个数字删去并将当前字符加入结果集中；否则，保留结果集最后一个字符，然后将该字符加入结果集中。这可以看成是关注"局部最优"从而达到"全局最优"的思路。
• 该题应该使用的是单调栈的解法，代码如下：

    public String removeKdigits(String num, int k) {
        int len = num.length();
        //corner case
        if(k==len)        
            return "0";
            
        Stack<Character> stack = new Stack<>();  //单调栈，栈底到栈顶递增
        int i =0;
        while(i<num.length()){
            //whenever meet a digit which is less than the previous digit, discard the previous one
            while(k>0 && !stack.isEmpty() && stack.peek()>num.charAt(i)){
                stack.pop();
                k--;
            }
            stack.push(num.charAt(i));
            i++;
        }
        
        // corner case like "1111"，当有相同元素时，总删除栈顶的元素才能保证最后的结果最小，因为栈是递增的，若删除的是栈底元素，则要比删除栈顶元素的结果大
        while(k>0){
            stack.pop();
            k--;            
        }
        
        //construct the number from the stack
        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty())
            sb.append(stack.pop());
        sb.reverse();
        
        //remove all the 0 at the head
        while(sb.length()>1 && sb.charAt(0)=='0')
            sb.deleteCharAt(0);
        return sb.toString();
    }

16？？.（未做）（770:Hard）Basic Calculator IV

• 太复杂，要毕设答辩没做，下次复习时再做，该题同样也属于String类题目，当时也没做。

17.（316:Hard）（非常经典题）Remove Duplicate Letters

• 该题需要注意：字典序最小的序列必须是存在于字符串中的，不能是自己取每个distinct字符然后自己排序然后返回，而这个排序后的序列可能不存在与字符串中。
• 该题参考的Discuss中高票答案，思路如下：

The basic idea is to find out the smallest result letter by letter (one letter at a time). Here is the thinking process for input "cbacdcbc":

1. find out the last appeared position for each letter;

数字代表每个字母最后一次出现的位置
    c - 7
    b - 6
    a - 2
    d - 4

2. find out the smallest index from the map in step 1 (a - 2); 找出map中最小的索引，即某个字母最后一次出现的位置位于最前面
3. the first letter in the final result must be the smallest letter from index 0 to index 2; 从[0,2]中找出最小的字母，因为a最后在2处出现，所以必须在[0,2]中选一个字母
4. repeat step 2 to 3 to find out remaining letters.

    the smallest letter from index 0 to index 2: a
    the smallest letter from index 3 to index 4: c
    the smallest letter from index 4 to index 4: d
    the smallest letter from index 5 to index 6: b

so the result is "acdb"

Notes:

1. after one letter is determined in step 3, it need to be removed from the "last appeared position map", and the same letter should be ignored in the following steps
2. in step 3, the beginning index of the search range should be the index of previous determined letter plus one,end指针可能后移，也可能不后移，比如[0,2]中存在字母比'a'还小，则搜索区域截止的位置不变，只改变搜索的起始位置(该选定字符索引下标加1)

该题被分为Greedy贪心算法类题目，"贪心"体现的位置可能在于指定搜索区域内找出最小字母，下次复习时与同学讨论请教。此外该题应该还有其他思路，下次复习时再研究学习

18.（853:Medium）（非常经典题）Car Fleet

• Calculate time needed to arrive the target, sort by the start position. Loop on each car from the end to the beginning since a car can never pass another car ahead of it, but it can catch up to it, and drive bumper to bumper at the same speed 越靠近终点的车辆越可能最先到达. cur records the current biggest time (the slowest). If another car needs less or equal time than cur, it can catch up this car. Otherwise it will become the new slowest car, that is new lead of a car fleet 到达时间越长的车辆越可能成为制约后边车辆的fleet.

19.（1047:Easy）（经典题）Remove All Adjacent Duplicates In String

• 用stack来解决这个问题非常容易和巧妙。

20.（1019:Medium）（非常非常经典题）Next Greater Node In Linked List

• 该题是非常典型的单调栈的问题，具体代码思路如下：

//该题是非常典型的单调栈问题
public int[] nextLargerNodes(ListNode head) {
    ArrayList<Integer> A = new ArrayList<>();
    for (ListNode node = head; node != null; node = node.next)
        A.add(node.val);
    int[] res = new int[A.size()];
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < A.size(); ++i) {
        while (!stack.isEmpty() && A.get(stack.peek()) < A.get(i))
            res[stack.pop()] = A.get(i);
        stack.push(i);
    }
    return res;
}

21.（1021:Easy）Remove Outermost Parentheses

• 该题感觉也可以用stack来求解，stack中存入括号的index，当最后左括号只剩一个时，利用substring函数求得。此外也可以利用以下方法：

public String removeOuterParentheses(String S) {
    StringBuilder s = new StringBuilder();
    int opened = 0;
    for (char c : S.toCharArray()) {
        if (c == '(' && opened++ > 0) s.append(c);
        if (c == ')' && opened-- > 1) s.append(c);
    }
    return s.toString();
}

22.（388:Medium）（非常经典题）Longest Absolute File Path

• 注意：需要事先明确的一点是，"\t"的长度是1而不是2，因为\是用来转义用的，有效的字符只是t
• 核心思路：我们以"\n"作为分隔符，"\t"的个数作为当前子路径所在的level数，调用lastIndexOf("\t")的String API可以计算出当前子路径有多少个"\t"，属于哪个level，之后stack.pop直到stack的顶端存储的是当前level的路径前缀，然后拼接计算新路径长度。

//需要事先明确的一点是，"\t"的长度是1而不是2，因为\是用来转义用的，有效的字符只是t
public int lengthLongestPath(String input) {
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(0); // "dummy" length
    int maxLen = 0;
    for(String s:input.split("\n")){
        int lev = s.lastIndexOf("\t")+1; // number of "\t"，注意"\t"的长度为1
        // 假设当前是level3，那么stack中只能存储level1和level2的前缀，且包括dummy length，总共stack的size应为3
        while(lev+1 != stack.size()) stack.pop(); // find parent，+1代表一开始我们新加入的dummy length "0"
        int len = stack.peek()+s.length()-lev+1; // remove "/t", add"/", 1代表"/"的长度
        stack.push(len);
        // check if it is file
        if(s.contains(".")) maxLen = Math.max(maxLen, len-1); //-1代表减去文件后缀之后添加的"/"的长度
    }
    return maxLen;
}