1. 每日温度(单调栈)

题目地址：https://leetcode-cn.com/problems/daily-temperatures/
题目 ：请根据每日气温列表temperatures，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用0来代替。

示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

解法一 ： 比较容易想到的方法是暴力解法，遍历每一个元素，并依次在后边的元素中查找大于该元素的位置，下边是我实现的代码 ：

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] ans = new int[temperatures.length] ;
        for (int i=0 ;i<temperatures.length ; i++){
            for(int j=i+1 ;j<temperatures.length ;j++){
                if(temperatures[j] > temperatures[i]){
                    ans[i] = j-i;
                    break;
                }
                ans[i] = 0 ;
            }
        }
        return ans ;
    }
}

这种方法时间复杂度很高，估计面试给出也不会是期望答案。
解法二：
首先，介绍单调栈数据结构。 单调递增栈 ：从栈底到栈顶是从大到小。单调递减栈 ：从栈底到栈顶是从小到大。
如果压栈元素 <= 栈顶元素，那么入栈 ；否则弹出栈顶元素。 很明显该题目使用的就是单调递增栈。 因为最终要输出的是第一个比该数大的数的下标，所以栈里边存的是元素的位置，而不是元素本身。在输出结果时，计算一下当前遍历的元素的位置i和栈内存储的位置的差（i-cur），就是要写入目标数组的元素。这里要注意每次从栈弹出元素时，目标数组写入一个值。

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int tempLength = temperatures.length ;
        int[] ans = new int[tempLength] ;
        Stack<Integer> stack = new Stack<>() ;
        for(int i=0 ;i<tempLength ;i++){
            if(stack.isEmpty() || temperatures[i] <= temperatures[stack.peek()]){
                stack.push(i);
            }
            else{
                while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]){
                    int cur = stack.pop() ;
                    ans[cur] = i - cur ;
                }
                stack.push(i) ;
            }
        }
        return ans ;
    }
}

2. 螺旋矩阵(矩阵、模拟)

题目地址： https://leetcode-cn.com/problems/spiral-matrix/
题目 ： 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。下边是一个示例：

这道题个人感觉还是比较难的，我自己尝试了一个种方法，先向右再向下再向左再向上挪一步，其间碰到矩阵的边界，或者碰到已经访问过的格子，就转向。但是提交后发现并不正确，如果绕大圈需要从底往上到第一个元素才能转向，这时候优先向上而不是向右。可见第一次的思路还是有问题的，看了题解的答案，发现大部分代码我还是想到了，例如方向、例如创建一个mn的矩阵保存哪些格子访问过。最关键的一点，不是没步骤按优先级，而是把一个方向走到头之后换方向*。
下边的代码是我的实现 ：

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        //保存输出结果数组
        int rl = matrix.length , cl = matrix[0].length ;
        List<Integer> ans = new ArrayList<>() ;
        //建立矩阵记录哪些被访问过
        int[][] visited = new int[rl][cl];
        int vt=1 ,m=0 , n=0;
        //初始化第一个元素matrix[0][0] 先开始。
        visited[m][n] = 1 ;
        ans.add(matrix[m][n]) ;
        //顺时针，先往右挪，再往下挪，再往左挪，再往上挪。
        int[][] directions = new int[][]{{0,1},{1,0},{0,-1},{-1,0}} ;
        int initDirection = 0 ;  //初始往右
        while(vt < rl*cl){
            int nextRow = m + directions[initDirection][0] ;
            int nextColumn = n + directions[initDirection][1];
            if(nextRow < 0 || nextRow == rl || nextColumn <0 || nextColumn == cl || visited[nextRow][nextColumn] == 1){
                //达到边界后，换一个方向
                initDirection = (initDirection + 1)%4 ;
            }
            m+=directions[initDirection][0] ;
            n+=directions[initDirection][1] ;
            ans.add(matrix[m][n]) ;
            //标记为访问过
            visited[m][n] = 1 ;
            vt++ ;
        }
        return ans ;
    }
}

这道题目确实考验对数组API的使用熟练度，我有以下的积累，希望后边能用到 ：

1.数组初始化、之后赋值的方法 ：
int[] intArr;
intArr = new int[]{1,2,3,4,5,9};
2.求二维数组的行和列 ：
行数 = matrix.length ， 列数 = matrix[0].length

3. 最长递增子序列（动态规划）

题目：https://leetcode-cn.com/problems/longest-increasing-subsequence/
动态规划是一类重要而且常出的题目。 动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划类题目需要考虑能否将问题规模减小，将问题规模减小的方式有很多种，一些典型的减小方式是动态规划分类的依据，例如线性，区间，树形等。数组上常用的减少规模的方式包括：每次减少一半/每次减少一个。

解决动态规划问题最难的地方有两点：
如何定义 f(n)
如何通过 f(1), f(2), … f(n - 1) 推导出 f(n)，即状态转移方程。

该题目找最长严格递增子序列，拆解子问题时，可以从只包含第一个元素开始迭代，每次找i的dp状态值是，从0到i-1迭代dp[j] + 1 (如果a[i] > a[j] ，否则不加1)，这样就找到转移方程了。 我在纸上描述了状态转移方程如下 ：

这样代码就好写了，下边是代码，调试过程中我遇到了几个问题：1.dp方程的元素并不是单调递增的，例如原始序列[1,3,6,4,2] ，dp[4] = 2 并不等于 dp[3] + 0 。 2. dp[0] 需要初始化为1 否则它之前没有可比较的数字。

class Solution {
    public int lengthOfLIS(int[] nums) {
                //边界情况
        int len = nums.length ;
        if (len == 0) return 0 ;
        //状态转移方程   f(i) = max{f(j)} + 1
        int[] dp = new int[len] ;
        dp[0] = 1 ; 
        int ans =  0 ; 
        for (int i=1 ; i<len ;i++){
            int maxLIS = 1;  //最小是1 
            for (int j=0 ; j < i ;j++ ){
                if (nums[j] < nums[i] ) {
                    maxLIS = Integer.max(maxLIS,dp[j] + 1 ) ;
                }
            }
            dp[i] = maxLIS ;
        }
        for(int tp : dp) ans = Integer.max(ans,tp) ; 
        return ans ; 
    }
}

4.乘积最大子数组（动态规划）

https://leetcode-cn.com/problems/maximum-product-subarray/
给你一个整数数组 nums，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例 1:
输入: [2,3,-2,4]
输出: 6
解释:子数组 [2,3] 有最大乘积 6。

该题目也可以使用DP解决，线性DP，使用前一个位置计算。这里最大乘积会相对复杂一点，如果前一个数字是一个负数并且绝对值很大，如果第i个位置也是负数，负负得正。也可能得到正确答案，所以，我这里除了新建一个dp[]来保存最大值外，还定义了一个minDp[]来保存最小值，每次计算一个最大值一个最小值，分别存在这2个数组里。 下边是我理解的动态转移方程：

class Solution {
    public int maxProduct(int[] nums) {
        int len = nums.length ;
        if(len ==0 ) return  0 ;
        int[] dp = new int[len] ;
        int[] minDp = new int[len] ;
        dp[0] = nums[0] ;
        minDp[0] = nums[0] ;
        for(int i =1 ;i <len ;i++){
            dp[i] = Integer.max(nums[i] , Integer.max(nums[i]*dp[i-1] , nums[i]*minDp[i-1])) ;
            minDp[i] = Integer.min(nums[i] , Integer.min(nums[i]*dp[i-1] , nums[i]*minDp[i-1])) ;
        }
        int ans = Integer.MIN_VALUE ;
        for (int k=0 ;k<len ;k++){
            ans = Integer.max(ans,dp[k]) ;
        }
        return ans ;
    }
}

5.打家窃舍（动态规划）

题目地址： https://leetcode-cn.com/problems/house-robber/
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

该题目是典型的dp问题，相比前边的最大和的子数组问题，难点在于，不能取相邻的数组的数字，这里就需要找下规律，并改下动态规划方程。 这里dp[0] 就是第一个元素（这里不解释）。 dp[1] 应该是 max (dp[0] , nums[1]) 第2个元素可能是第一个元素，也可能是第2个元素。
一般情况下的动态转移方程是 ：
dp[i]=max(dp[i−2]+nums[i],dp[i−1]) ，加上上边说的边界条件 ：
边界条件为：
dp[0]=nums[0]
dp[1]=max(nums[0],nums[1])
分析到这里，代码就太好写了，下边是我的实现 ：

        int len = nums.length ;
        if (len == 1) return nums[0] ;

        int[] dp = new int[len] ;
        dp[0] = nums[0] ;
        dp[1] = Integer.max(dp[0], nums[1]) ;
        int ans = Integer.max(dp[0], dp[1]) ;
        for (int i=2;i <len ;i++){
            dp[i] = Integer.max(dp[i-2] + nums[i] , dp[i-1]) ;
            ans = Integer.max(ans,dp[i]);
        }
        return ans ;

6.打家劫舍II

题目地址：https://leetcode-cn.com/problems/house-robber-ii/solution/da-jia-jie-she-ii-by-leetcode-solution-bwja/
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

这个题目跟题目5相似，但是不能是首位相接，如何才能保证第一间房屋和最后一间房屋不同时偷窃呢？如果偷窃了第一间房屋，则不能偷窃最后一间房屋，因此偷窃房屋的范围是第一间房屋到最后第二间房屋；如果偷窃了最后一间房屋，则不能偷窃第一间房屋，因此偷窃房屋的范围是第二间房屋到最后一间房屋。
数组nums的长度为n。如果不偷窃最后一间房屋，则偷窃房屋的下标范围是[0,n-2]；如果不偷窃第一间房屋，则偷窃房屋的下标范围是[1,n-1]。
下面是我实现的代码：

class Solution {
    public int rob(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        } else if (length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
    }

    public int robRange(int[] nums, int start, int end) {
        int first = nums[start], second = Math.max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
}

7. 最长等差子序列 ：

这个类型的题目是一个扩展动态规划，动态转移方程结果使用哈希表来存储。 先看原始简单第一题：
https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference/
该题目，要找存在的最长等差子序列，并且给了固定长度的“等差” 。 那么使用一个HashMap来保存状态，Key就是原始数组里的值，value就是截止到dp[i]为止，最大的等差子序列的长度。这里是实现用Put时候，如果有比该值小于固定等差的key时，其value就加1，否则重新从1开始。代码如下：

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        int len = arr.length ;
        if(len == 1) return 1;
        Map<Integer,Integer> dp = new HashMap<>() ;
        int maxDp = 0;
        for (int vd : arr){
            int gsp = dp.getOrDefault(vd - difference , 0) +1 ;
            dp.put(vd, gsp);
            maxDp = Integer.max(gsp,maxDp) ;
        }
        return maxDp ; 
    }
}

那下边的非定长等差数列就是上边题目的一个升级了，没有提供出定长的“等差”。
https://leetcode-cn.com/problems/longest-arithmetic-subsequence/

这里的方法也比较巧妙，我先用一个Set枚举出所有可能的“等差”(longestArithSeqLength函数中定义)， 再每一个等差带入上边的函数中，再从每个输出结果中选出最大的，虽然感觉这种方法较笨，但是也能解决问题。代码如下：

class Solution {

    public int longestSubsequence(int[] arr, int difference) {
        int len = arr.length ;
        if(len == 1) return 1;
        Map<Integer,Integer> dp = new HashMap<>() ;
        int maxDp = 0;
        for (int vd : arr){
            int gsp = dp.getOrDefault(vd - difference , 0) +1 ;
            dp.put(vd, gsp);
            maxDp = Integer.max(gsp,maxDp) ;
        }
        return maxDp ;
    }


    public int longestArithSeqLength(int[] nums) {
        int len = nums.length ;
        //保存可能出现的等差
        Set<Integer> allDis = new HashSet<>() ;
        int i=0 ,j=0 ;
        for (i=0 ;i<len ;i++){
            for (j=i+1 ; j<len ;j++){
                allDis.add(nums[j] - nums[i]) ;
            }
        }
        int ans = 0 ;
        for(int dis : allDis){
            ans = Integer.max(ans,longestSubsequence(nums,dis)) ;
        }
        return ans ;
    }
}

8. N叉树的遍历问题（深度优先遍历DFS） ：

关于树的遍历，我们很快就想到了DFS，这也是深度优先遍历的典型题目。 下面摘取了Leetcode上关于DFS的一些知识的介绍，可以先做扫盲吧。

深度优先遍历
1.只要前面有可以走的路，就会一直向前走，直到无路可走才会回头；
2.「无路可走」有两种情况：① 遇到了墙；② 遇到了已经走过的路；
3.在「无路可走」的时候，沿着原路返回，直到回到了还有未走过的路的路口，尝试继续走没有走过的路径；
4.有一些路径没有走到，这是因为找到了出口，程序就停止了；
5.「深度优先遍历」也叫「深度优先搜索」，遍历是行为的描述，搜索是目的（用途）；
遍历不是很深奥的事情，把 所有 可能的情况都看一遍，才能说「找到了目标元素」或者「没找到目标元素」。遍历也称为 穷举，穷举的思想在人类看来虽然很不起眼，但借助 计算机强大的计算能力，穷举可以帮助我们解决很多专业领域知识不能解决的问题。
「遍历」和「搜索」可以看作是两个的等价概念，通过遍历 所有 的可能的情况达到搜索的目的。遍历是手段，搜索是目的。因此「深度优先遍历」也叫「深度优先搜索」。

leetcode 上的dfs问题，直接想到递归解决就行了。下面列举了一道N叉树的前序遍历题目，我也是按照递归来解决的。
https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/

class Solution {

    private void traverse(Node root, List<Integer> mylist){
        mylist.add(root.val) ; 
        if (root.children.size() > 0){
            for (Node c : root.children){
                traverse(c,mylist); 
            }
        }
    }

    public List<Integer> preorder(Node root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) return ans;
        traverse(root,ans) ; 
        return ans ; 
    }
}

那么同样地，还有N叉树的后续遍历的一道题目，也一起做了。
https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/

class Solution {
    private void traverse(Node root, List<Integer> mylist){
        if (root.children.size() > 0){
            for (Node c : root.children){
                traverse(c,mylist); 
            }
        }
        mylist.add(root.val) ; 
    }

    public List<Integer> postorder(Node root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) return ans;
        traverse(root,ans) ; 
        return ans ; 
    }
}