class Solution {
    public int firstMissingPositive(int[] nums) {
        int missedNumber = nums.length+1;
        for(int i = 0; i < nums.length; i++){
            /*注意是while
            当发现位置上的数并不符合条件时，就建立循环把每一位换来的数字送往应该在的位置
            若目标位置上已经是正确的数字则不必改动*/
            while (nums[i] > 0 && nums[i] < nums.length && nums[i] != nums[nums[i]-1]){
                
                //和最终位置上的数字交换
                int temp = nums[nums[i]-1];
                nums[nums[i]-1] = nums[i];
                nums[i] = temp;
            }
        }
        for(int i = 0; i < nums.length; i++){
            if(nums[i] != i+1) {
                missedNumber = i + 1;
                break;
            }
        }
        return missedNumber;
    }
}

class Solution {
    //事实上，这是一个bfs
    //Input = [2,3,1,1,4]
    //第一层 2 （起始位置数字） 第一层能到达的最远数字是3,1。其中1是最远位置数字
    //第二层 3 1 第二层能到达的最远数字是1,1,4。其中4是最远位置数字
    //一共跳了两次（到达第一层最后一个数字2跳一次，到达第二层最后一个数字3跳一次）
    //Note: You can assume that you can always reach the last index.
    public int jump(int[] nums) {
        int jumps = 0;
        int curEnd = 0;//当前层的最后一个位置
        int curFarthest = 0;//用来记录当前层跳一次能到达的最远位置（也就是下一层的最后一个位置）
        //注意i<=nums.length-2。因为我们最终要落在倒数第二层上,由倒数第二层跳到nums.length-1位置。nums.length-1即最末位4肯定在倒数第一层上
        for (int i = 0; i < nums.length - 1; i++) {
            curFarthest = Math.max(curFarthest, i + nums[i]);//比较本层最远能跳到什么位置
            if (i == curEnd) {//到达这一层的最后一个位置后，该进入下一层了
                jumps++;//跳到了下一层
                curEnd = curFarthest;//下一层的结束位置是上一层所能到达的最远位置
            }
            //如果第k层的curFarthest>=nums.length-1了,那么说明向下跳一层就能完成任务了。
            //因此，在k层的最后一个位置，我们进行jumps++和curEnd=curFarthest操作进入第k+1层之后，再也不会向下跳了:
            //因为i==curEnd不可能被满足了(i<=nums.length-2 而 curEnd>=nums.length-1)

            //下面这个判断不加也行(只要继续i++自然会退出循环), 加了反而更慢(可能是因为if判断耗时比较多)
            // if(curEnd>=nums.length-1) break;
        }
        return jumps;
    }
}

class Solution {
    public int maxProfit(int[] prices) {
        int hold1stValue = Integer.MAX_VALUE;
        int Assume1stProfit = 0;
        int hold2ndValue = Integer.MAX_VALUE;
        int OverallProfit = 0;
        for(int currentPrice: prices) {
            hold1stValue = Math.min(hold1stValue, currentPrice);
            Assume1stProfit = Math.max(Assume1stProfit, currentPrice - hold1stValue);
            hold2ndValue = Math.min(hold2ndValue, currentPrice - Assume1stProfit);
            OverallProfit = Math.max(OverallProfit, currentPrice - hold2ndValue);
        }
        return OverallProfit;
    }
}

class Solution {
    public int maxProfit(int k, int[] prices) {
        if (k >= prices.length / 2) return greedy(prices);
        int[][] DP = new int[k + 1][prices.length];
        for (int i = 1; i <= k; i++) {
            int tmpMax =  -prices[0];
            for (int j = 1; j < prices.length; j++) {
                DP[i][j] = Math.max(DP[i][j - 1], prices[j] + tmpMax);
                tmpMax =  Math.max(tmpMax, DP[i - 1][j - 1] - prices[j]);
            }
        }
        return DP[k][prices.length - 1];
    }
    private int greedy(int[] prices) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++)
            if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
        return profit;
    }
}

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        for (int i = 1; i < height.length - 1; i++){
            int maxLeft = 0, maxRight = 0;
            for (int j = i; j >= 0; j--)//j = i 可能本身是左隔板
                maxLeft = Math.max(height[j], maxLeft);
            for (int j = i; j < height.length; j++) 
                maxRight = Math.max(height[j], maxRight);
            ans += Math.min(maxLeft, maxRight) - height[i];
        }
        return ans;
    }
}

class Solution {
    public int trap(int[] height) {
        if(height.length == 0)
            return 0;
        int ans = 0;
        int[] left_max = new int[height.length];int[] right_max = new int[height.length];
        left_max[0] = height[0];right_max[height.length - 1] = height[height.length - 1];
        for (int i = 1; i < height.length; i++) {
            left_max[i] = Math.max(height[i], left_max[i - 1]);
        }
        for (int i = height.length - 2; i >= 0; i--) {
            right_max[i] = Math.max(height[i], right_max[i + 1]);
        }
        for (int i = 1; i < height.length - 1; i++) {
            ans += Math.min(left_max[i], right_max[i]) - height[i];
        }
        return ans;
    }
}

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right){
            if(leftMax > height[left]){
                ans += leftMax - height[left];
            }else leftMax = height[left];

            if(rightMax > height[right]){
                ans += rightMax - height[right];
            }else rightMax = height[right];

            if(height[left] < height[right]) left++;
            else right--;
        }
        return ans;
    }
}

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int longestStreak = 1;
        int currentStreak = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i-1]) {
                if (nums[i] == nums[i-1]+1) {
                    currentStreak += 1;
                }
                else {
                    longestStreak = Math.max(longestStreak, currentStreak);
                    currentStreak = 1;
                }
            }
        }
        return Math.max(longestStreak, currentStreak);
    }
}

class Solution {
    private boolean arrayContains(int[] arr, int num) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == num) {
                return true;
            }
        }

        return false;
    }
    public int longestConsecutive(int[] nums) {
        int longestStreak = 0;

        for (int num : nums) {
            int currentNum = num;
            int currentStreak = 1;

            while (arrayContains(nums, currentNum + 1)) {
                currentNum += 1;
                currentStreak += 1;
            }

            longestStreak = Math.max(longestStreak, currentStreak);
        }

        return longestStreak;
    }
}

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            num_set.add(num);
        }

        int longestStreak = 0;

        for (int num : num_set) {
            if (!num_set.contains(num-1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (num_set.contains(currentNum+1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
}

if (nums.length < 2)return 0;
        int maxDiff = 0;
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++){
            maxDiff = Math.max(maxDiff, nums[i] - nums[i - 1]);
        }
        return maxDiff;

class Solution {
    public int maximumGap(int[] nums) {
        if (nums.length < 2)return 0;
        int min = nums[0], max = nums[0];
        for (int i : nums){
            min = Math.min(min, i);
            max = Math.max(max, i);
        }
        int gap = (int)Math.ceil((double)(max - min) / (nums.length - 1));
        if (gap == 0)return 0;
        int[] bucketMin = new int[nums.length]; int[] bucketMax = new int[nums.length];
        Arrays.fill(bucketMax, Integer.MIN_VALUE); Arrays.fill(bucketMin,Integer.MAX_VALUE);
        for(int i : nums){
            int index = (i - min )/ gap;
            bucketMin[index] = Math.min(bucketMin[index], i);
            bucketMax[index] = Math.max(bucketMax[index], i);
        }
        int maxGap = Integer.MIN_VALUE;
        int previousMax = min;
        for (int i = 0; i < bucketMin.length; i++){
            if(bucketMin[i] != Integer.MAX_VALUE){
                maxGap = Math.max(maxGap, bucketMin[i] - previousMax);
                previousMax = bucketMax[i];
            }
        }
        return maxGap;
    }
}

class Solution {
    public int candy(int[] ratings) {
        int[] candies = new int[ratings.length];
        Arrays.fill(candies, 1);
        boolean flag = true;
        int sum = 0;
        while (flag) {
            flag = false;
            for (int i = 0; i < ratings.length; i++) {
                if (i != ratings.length - 1 && ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
                    candies[i] = candies[i + 1] + 1;
                    flag = true;
                }
                if (i > 0 && ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) {
                    candies[i] = candies[i - 1] + 1;
                    flag = true;
                }
            }
        }
        for (int candy : candies) {
            sum += candy;
        }
        return sum;
    }
}

class Solution {
    public boolean isScramble(String s1, String s2) {
        if(s1.length() != s2.length())return false;
        //pruning
        if (s1.equals(s2)) return true;
        //判断是否不是同字母异构
        int[] count = new int[256];
        for (int i = 0; i < s1.length(); i++){
            count[s1.charAt(i)]++;
            count[s2.charAt(i)]--;
        }
        for (int i = 0; i < s1.length(); i++){
            if(count[s1.charAt(i)] != 0)return false;
        }
        for (int i = 1; i < s1.length(); i++){
            String s1Left = s1.substring(0, i);
            String s2Left = s2.substring(0, i);
            String s1Right = s1.substring(i);
            String s2Right = s2.substring(i);
            //在当前分割处没有交换
            if(isScramble(s1Left, s2Left) && isScramble(s1Right, s2Right))
                return true;
            //在当前分割处左右交换
            s2Left = s2.substring(0, s2.length() - i);
            s2Right = s2.substring(s2.length() - i);
            if(isScramble(s1Left, s2Right) && isScramble(s1Right, s2Left))
                return true;
        }
        return false;
    }
}

class Solution {
    public String removeDuplicateLetters(String s) {
        if (s.length() == 0)return "";
        int[] count = new int[26];
        int smallestPosition = 0;
        for (int i = 0; i < s.length(); i++){
            count[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < s.length(); i++){
            if (s.charAt(i) < s.charAt(smallestPosition)) smallestPosition = i;//在前置中找出最小的
            if (--count[s.charAt(i) - 'a'] == 0){//消除前置重复，剩余的字符串的第一位在剩余字符串中无重复
                break;
            }
        }
        return s.charAt(smallestPosition) + removeDuplicateLetters(s.substring(smallestPosition + 1)
                .replaceAll("" + s.charAt(smallestPosition), ""));//在后置字符串中清除目前遇到的最小字符串
    }
}

private final String[] LESS_THAN_20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    private final String[] TENS = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    private final String[] THOUSANDS = {"", "Thousand", "Million", "Billion"};
    public String numberToWords(int num) {
        if (num == 0)return "Zero";
        int i = 0; String result = "";
        while (num > 0){
            if(num % 1000 != 0){
                result = extractEndThree(num % 1000) + THOUSANDS[i] +" "+ result;
            }
            num /= 1000;
            i++;
        }
        return result.trim();
    }
    private String extractEndThree(int num){
        if(num == 0) return "";
        else if (num < 20)return LESS_THAN_20[num] + " ";
        else if (num < 100) return TENS[num / 10] + " " + extractEndThree(num % 10);
        else
            return LESS_THAN_20[num / 100] + " Hundred " + extractEndThree(num % 100);
    }

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> postOrder = new LinkedList<Integer>();
        if (root != null) {
            postOrder.addAll(postorderTraversal(root.left));
            postOrder.addAll(postorderTraversal(root.right));
            postOrder.add(root.val);
        }
        return postOrder;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> postOrder = new LinkedList<Integer>();
        Stack<TreeNode> stack = new Stack<>();
        if(root == null) return postOrder;
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode current = stack.pop();
            postOrder.add(0, current.val);
            if (current.left != null)
                stack.push(current.left);
            if (current.right != null)
                stack.push(current.right);
        }
        return postOrder;
    }
}

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1, mid;
        while (left <= right){
            mid = left + (right - left) / 2;
            if (nums[mid] < nums[right]) right = mid;
            else if (nums[mid] > nums[right]) left = mid + 1;
            else right = right - 1;
        }
        return nums[left];
    }
}

class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        int[][] direction = {{0,1},{1,0},{0,-1},{-1,0}};
        int row = matrix.length;
        if (row == 0) return 0;
        int col = matrix[0].length;

        int[][] grid = new int[row + 2][col + 2];
        for (int i = 0; i < row; i++){
            System.arraycopy(matrix[i],0, grid[i+1], 1, col);
        }

        //计算出入度
        int[][] outdegree = new int[row+2][col+2];
        for (int i = 1; i <= row; i++){
            for (int j = 1; j <= col; j++){
                for (int[] d : direction){
                    if (grid[i][j] < grid[i + d[0]][j + d[1]]) outdegree[i][j]++;
                }
            }
        }

        row += 2; col += 2;
        List<int[]> leaves = new ArrayList<int[]>();
        for (int i = 1; i < row - 1; i++){
            for (int j = 1; j < col - 1; j++){
                if (outdegree[i][j] == 0) leaves.add(new int[]{i,j});
            }
        }

        int height = 0;
        while (!leaves.isEmpty()){
            height++;
            List<int[]> newLeaves = new ArrayList<int[]>();
            for (int[] node : leaves){
                for (int[] dir : direction){
                    int x = node[0] + dir[0], y = node[1] + dir[1];
                    if (grid[node[0]][node[1]] > grid[x][y]){
                        if (--outdegree[x][y] == 0) newLeaves.add(new int[]{x,y});
                    }
                }
            }
            leaves = newLeaves;
        }
        return height;
    }
}