二刷Leetcode-Days07

动规：

    /**
     * 70. 爬楼梯
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = 2;
        for (int i = 2; i < n; i++) {
            // n 阶可以拆成最小子问题 n-1 阶和 n-2 阶
            // 每一步只能走1阶或2阶，所以3阶的走法可以看成是：1阶走2步 + 2阶走1步，可以理解为 => 当前状态只与前两个状态有关
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n - 1];
    }

    /**
     * 746. 使用最小花费爬楼梯
     * @param cost
     * @return
     */
    public static int minCostClimbingStairs(int[] cost) {
        // 1、dp[] 表示走到当前台阶需要花费的最小费用
        int[] dp = new int[cost.length + 1];
        // 3、可以选择从下标为 0 或 1 开始爬，开始爬不支付费用
        dp[0] = 0;
        dp[1] = 0;
        // 2、dp[i] 显然和前两个状态有关，取前两个状态值的最小值，这里要注意费用的计算是以离开时算的
        for (int i = 2; i <= cost.length; i++) {
            // dp[i-1] 和 cost[i-1] 相关，dp[i-2]和cost[i-2]相关
            // 因为只有离开某一台阶后才计算它的费用，仅仅落在上面不计算，题目里也是这个意思
            dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
        }
        return dp[cost.length];
    }

    /**
     * 496. 下一个更大元素 I
     *
     * @param nums1
     * @param nums2
     * @return 没有重复元素的两个数组
     */
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];
        Arrays.fill(res, -1);
        // 先用 map 存储目标数组的值
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            hashMap.put(nums1[i], i);
        }
        // 单调栈找出 nums2 的值
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for (int i = 1; i < nums2.length; i++) {
            if (nums2[i] > nums2[stack.peek()]) {
                while (!stack.isEmpty() && nums2[i] > nums2[stack.peek()]) {
                    if (hashMap.containsKey(nums2[stack.peek()])){
                        Integer index = hashMap.get(nums2[stack.peek()]);
                        res[index] = nums2[i];
                    }
                    stack.pop();
                }
            }
            stack.add(i);
        }
        return res;
    }