LeetCodeTop100高频题目解答

public int[] twoSum(int[] nums, int target) {      
    Map<Integer, Integer> numToIndex = new HashMap<>();
    int len = nums.length;
    int[] result = new int[2];
    for (int i = 0; i < len; i++) {
        if (numToIndex.containsKey(nums[i])) {
            result[0] = numToIndex.get(nums[i]);
            result[1] = i;
            return result;
        } else {
            numToIndex.put(target-nums[i], i);
        }
    }
    return new int[2];
}

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode head = new ListNode(0);
    ListNode next = head;

    int sum = 0;
    while(l1 != null || l2 != null) {
        sum /= 10;
        if(l1!=null) {
            sum += l1.val;
            l1 = l1.next;
        }

        if(l2 != null) {
            sum += l2.val;
            l2 = l2.next;
        }

        next.next = new ListNode(sum % 10);
        next = next.next;
    }

    if(sum / 10 == 1) next.next = new ListNode(1);

    return head.next;
}

public int lengthOfLongestSubstring(String s) {
    if(s.length() == 0 || s.length() == 1) return s.length();
    
    HashMap<Character, Integer> hashMap = new HashMap<>();
    int head = 0;
    int max = 0;
    for (int i = 0; i < s.length(); i++) {
        if(hashMap.containsKey(s.charAt(i))) {
            //跳过重复的字符串，重新设定新的head
            head = Math.max(hashMap.get(s.charAt(i))+1, head);
        }
        //实时更新最长不重复字符串
        max = Math.max(i-head+1, max);
        //重置每个字符最后出现的位置
        hashMap.put(s.charAt(i), i);
    }
    
    return max;
}

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int len1 = nums1.length;
    int len2 = nums2.length;

    int mid = (len1+len2)/2;
    boolean odd = (len1+len2)%2==0;
    int[] newNums = new int[len1+len2];

    int i1 = 0, i2 = 0;
    int modCount = 0;
    while(i1<len1 && i2<len2) {
        if(nums1[i1]<nums2[i2]) {
            newNums[modCount++] = nums1[i1++];
        } else {
            newNums[modCount++] = nums2[i2++];
        }

        if(modCount-1>mid) break;
    }

    while(modCount-1<mid) {
        if(i1<len1) newNums[modCount++] = nums1[i1++];
        if(i2<len2) newNums[modCount++] = nums2[i2++];
    }

    if(odd) return ((double)newNums[mid]+(double)newNums[mid-1])/2;
    else return (double)newNums[mid];
}

 public String longestPalindrome(String s) {
 	if(s.length() == 0 || s.length()==1) return s;
    if(s.length() == 2 && s.charAt(0) == s.charAt(1)) return s;
 
     //动态规划
     int left = 0, right = 1;
     int maxLength = 0;
     int len = s.length();
     boolean[][] check = new boolean[len][len];
     for(int i = 0; i < len; i+=1) {
         check[i][i] =true;

         for(int j = 0; j < i; j++) {
             check[j][i] = s.charAt(i)==s.charAt(j) && (i-j<2 || (i > 0 && check[j+1][i-1]));

             if(check[j][i]) {
                 if(i-j+1 > maxLength) {
                     maxLength = i - j + 1;
                     left = j;
                     right = i + 1;
                 }
             }
         }
     }

     return s.substring(left, right);
 }

public int maxArea(int[] height) {
    if (height == null || height.length <= 1) return 0;

    int len = height.length;
    int i = 0, j = len-1;
    int maxAre = 0;
    while (i < j) {
        maxAre = Math.max(Math.min(height[i], height[j])*(j-i), maxAre);

        if (height[i]<=height[j]) {
            i++;
        } else {
            j--;
        }
    }
    return maxAre;
}

public List<List<Integer>> threeSum(int[] nums) {
    int len = nums.length;
    Arrays.sort(nums);

    if (len < 3) return Collections.emptyList();
    List<List<Integer>> result = new ArrayList<>(len);

    for (int i = 0; i < len; i++) {
        if (i > 0 && nums[i] == nums[i-1]) {
            continue;
        }

        int start = i+1, end = len-1;
        while (start < end) {
            int sum = nums[i]+nums[start]+nums[end];
            if (sum > 0) {
                end--;
            } else if (sum < 0) {
                start++;
            } else {
                result.add(Arrays.asList(nums[i], nums[start], nums[end]));
                //                     List<Integer> temp = new ArrayList<>(3);
                //                     temp.add(nums[i]);
                //                     temp.add(nums[start]);
                //                     temp.add(nums[end]);
                //                     result.add(temp);
                // 跳过相同的组合
                for (start+=1; start < end && nums[start]==nums[start-1]; start++);
                for (end-=1; start < end && nums[end]==nums[end+1]; end--);
            }
        }
    }
    return result;
}

private String[] dig2char = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public List<String> letterCombinations(String digits) {
    List<String> result = new ArrayList<>();
    Deque<String> queue = new ArrayDeque<>();
    queue.add("");

    int len = digits.length();
    for (int i=0; i < len; i++) {
        String chars = dig2char[digits.charAt(i)-'0'];

        int size = queue.size();
        while (size>0) {
            String temp = queue.poll();
            size--;
            for (int j=0, charsLen = chars.length(); j < charsLen; j++) {
                queue.add(temp+chars.substring(j, j+1));
            }
        }
    }

    result.addAll(queue);

    return result;
}

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode fast = head, slow = head;
    for (int i = n; i>0; i--) {
        fast = fast.next;
    }
    if (fast == null) {
        return slow.next;
    }

    while (fast.next!=null) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;

    return head;

}

public boolean isValid(String s) {
    HashMap<Character, Character> hashMap = new HashMap<>();
    hashMap.put('(', ')');
    hashMap.put('[', ']');
    hashMap.put('{', '}');
    Stack<Character> stack = new Stack<>();
    int len = s.length();
    for(int i = 0; i < len; i++) {

        if(hashMap.containsKey(s.charAt(i))) {
            stack.push(s.charAt(i));//左括号添加
            continue;
        } else {
            if(stack.isEmpty()) return false;
        }
        if(hashMap.get(stack.peek()) == s.charAt(i)) {
            stack.pop();
        } else {
            return false;
        }
    }

    return stack.isEmpty();
}

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //写一种通用的解法，采用小顶堆，用在两个链表中会超时
//        PriorityQueue<Integer> heap = new PriorityQueue<>();
//        while (l1 != null) {
//            heap.add(l1.val);
//        }
//        while (l2 != null) {
//            heap.add(l2.val);
//        }
//
//        ListNode newHead = new ListNode(-1);
//        ListNode temp = newHead;
//        while (!heap.isEmpty()) {
//            temp.next = new ListNode(heap.poll());
//            temp = temp.next;
//        }
//
//        return newHead.next;

    //对于两个链表，采用简单的方式，不会超时，4ms
    ArrayList<Integer> arr = new ArrayList<>();
    while (l1 !=null && l2 != null) {
        if (l1.val < l2.val) {
            arr.add(l1.val);
            l1 = l1.next;
        } else {
            arr.add(l2.val);
            l2 = l2.next;
        }
    }

    while (l1 != null) {
        arr.add(l1.val);
        l1 = l1.next;
    }

    while (l2 != null) {
        arr.add(l2.val);
        l2 = l2.next;
    }

    // int size = arr.size();
    ListNode newHead = new ListNode(-1);
    ListNode temp = newHead;
    for (int num: arr) {
        temp.next = new ListNode(num);
        temp = temp.next;
    }

    return newHead.next;
}

public List<String> generateParenthesis(int n) {
    int left = n, right = n;
    List<String> result = new ArrayList<>();
    String temp = "(";
    generate(left - 1, right, result, temp);
    return result;
}

public void generate(int left, int right, List<String> result, String temp) {
    if(left == 0 && right == 0) result.add(temp);

    if(left > 0) {
        generate(left-1, right, result, temp+"(");
    }

    if(right > 0 && right > left) {//要在有左括号的情况，才能添加右括号
        generate(left, right-1, result, temp+")");
    }

}

public ListNode mergeKLists(ListNode[] lists) {

    if (lists == null || lists.length == 0) return null;
    if (lists.length == 1) return lists[0];

    PriorityQueue<ListNode> heap = new PriorityQueue<>(10,  new Comparator<ListNode>() {
        @Override
        public int compare(ListNode n1, ListNode n2) {
            return n1.val-n2.val;
        }
    });
    for (ListNode l1: lists) {
        if (l1 != null) heap.add(l1);//不要在for循环中再加while添加所有节点，容易超出内存限制
    }

    if (heap.size() == 0) return null;

    ListNode head = heap.poll(), temp = head;
    while (heap.size() > 0) {
        // 在这里在添加其他节点，主要是根据原来便是有序节点，所以起始节点必然是数组中的其中一个
        if (temp.next != null) heap.add(temp.next);
        temp.next = heap.poll();
        temp = temp.next;
    }

    return head;
}

public void nextPermutation(int[] nums) {
    if(nums==null || nums.length<2) return;

    int len = nums.length;
    int i = len-1;
    // 判断这个数组是否为递减数列
    while(i>0&&nums[i]<=nums[i-1]) {
        i--;
    }
    if(i==0) Arrays.sort(nums);// 如果是最大值了，直接获取最小值即可
    else {
        // 否则，直接找到i之后的大于nums[i-1]，进行交换，再将i之后的数字按递增排列
        for(int j = len-1; j>=0; j--) {
            if(nums[j]>nums[i-1]) {
                int temp = nums[j];
                nums[j] = nums[i-1];
                nums[i-1] = temp;
                break;
            }
        }

        Arrays.sort(nums, i, len);

    } 
}

public int longestValidParentheses(String s) {
    if (s == null || s.length() <= 1) {
        return 0;
    }

    int count = 0;
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(-1);
    for (int i = 0, len = s.toCharArray().length; i < len; i++) {
        if (s.charAt(i) == '(') {
            stack.push(i);
        } else {
            if (stack.isEmpty()) {
                stack.push(i);
            } else {
                stack.pop();//弹出左括号的位置或者-1
                count = Math.max(count, i-stack.peek());
            }
        }
    }

    return count;
}

public int[] searchRange(int[] nums, int target) {

    int[] result = new int[]{-1, -1};

    if (nums == null || nums.length == 0) return result;

    searchRange(nums, target, result, 0, nums.length);

    return result;
}

private void searchRange(int[] nums, int target, int[] result, int left, int right) {
    if (left > right) return;

    int middle = (left+right)/2;
    if (nums[middle] == target) {
        int leftIndex = middle, rightIndex = middle;
        while (leftIndex-1>=0 && nums[leftIndex-1] == target) {
            leftIndex -= 1;
        }
        while (rightIndex+1 < nums.length && nums[rightIndex+1] == target) {
            rightIndex += 1;
        }

        result[0] = leftIndex;
        result[1] = rightIndex;
    }

    if (nums[middle]>target) {
        searchRange(nums, target, result, left, middle);
    }

    if (nums[middle]<target) {
        searchRange(nums, target, result, middle, right);
    }

}

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>(candidates.length);
    if (candidates == null || candidates.length == 0) return result;

    List<Integer> temp = new ArrayList<>(candidates.length);
    combinationSum(candidates, target, result, temp, 0);
    return result;
}

private void combinationSum(int[] candidates, int target, List<List<Integer>> result, List<Integer> temp, int begin) {

    if (target < 0) return;
    if (target == 0) {
        result.add(new ArrayList<>(temp));
        return;
    }

    for (int i = begin, len = candidates.length; i < len; i++) {
        temp.add(candidates[i]);
        combinationSum(candidates, target-candidates[i], result, temp, i);
        temp.remove(temp.size()-1);
    }
}

public int trap(int[] height) {
    int n = height.length, left = 0, right = n-1;
    int lefth = 0, righth = 0, area = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            // 左边是从左往右看的，遇到右边比左边低时，才进行面积相加
            if (lefth <= height[left]) lefth = height[left];
            else area += (lefth-height[left]);
            left++;
        } else {
            // 右边是从右往左看的，遇到左边比右边低时，才进行面积相加
            if (righth <= height[right]) righth = height[right];
            else area += (righth-height[right]);
            right--;
        }
    }
    return area;
}

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();

    if(nums == null && nums.length == 0) return result;

    exchange(nums, 0, result);

    return result;
}

public void exchange(int[] nums, int index, List<List<Integer>> result) {
    if(index == nums.length-1) {
        List<Integer> temp = new ArrayList<>(nums.length);
        for(int n: nums) {
            temp.add(n);
        }
        result.add(temp);
        return;
    }

    for(int i = index; i < nums.length; i++) {
        swap(nums, index, i);//跟后面的元素交换
        exchange(nums, index+1, result);//探索下一种情况
        swap(nums, i, index);//交换，恢复回来的顺序，再去跟后面的其他元素交换，即固定在一个位置上不断跟其他元素进行交换
    }
}

public void swap(int[] nums, int i, int j) {
    int num = nums[i];
    nums[i] = nums[j];
    nums[j] = num;
}

public List<List<Integer>> permute(int[] nums) {
    //第二种做法
    if (nums == null || nums.length == 0) return new ArrayList<>();

    List<List<Integer>> result = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    if (nums.length == 1) {
        temp.add(nums[0]);
        result.add(temp);
        return result;
    }

    boolean[] flags = new boolean[nums.length];
    permute(nums, flags, temp, result);
    return result;
}

private void permute(int[] nums, boolean[] flags, List<Integer> temp, List<List<Integer>> result) {
    if (temp.size() == nums.length) {
        result.add(new ArrayList<>(temp));
    }

    for (int i = 0; i < nums.length; i++) {
        if (flags[i]) continue;
        flags[i] = true;
        temp.add(nums[i]);
        permute(nums, flags, temp, result);
        temp.remove(temp.size()-1);
        flags[i] = false;
    }

}

public List<List<String>> groupAnagrams(String[] strs) {
    List<List<String>> result = new ArrayList<>(strs.length);
    HashMap<String, List<String>> map = new HashMap<>();
    for (String str: strs) {
        char[] temp = str.toCharArray();
        Arrays.sort(temp);
        String s = new String(temp);
        if (map.containsKey(s)) {
            map.get(s).add(str);
        } else {
            List<String> l = new ArrayList<>();
            l.add(str);
            map.put(s, l);
        }
    }
    return new ArrayList<>(map.values());
}

public int maxSubArray(int[] nums) {
    //这道题有点像贪心算法
    if (nums == null && nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];

    int sum = nums[0];
    int max = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if(sum > 0) sum += nums[i];
        else sum = nums[i];

        max = Math.max(sum, max);

    }
    System.out.println(max);
    return max;
}

public boolean canJump(int[] nums) {
    if (nums == null) {
        return false;
    }
    if (nums.length == 0) {
        return true;
    }
    if (nums.length == 1) {
        return nums[0]>=0;
    }

    int len = nums.length, index = 0, max = 0;
    while (index < len) {
        if (index > max) {
            //如果下标比能跳的最大距离大的话，代表无法到达数组最后的位置
            return false;
        }

        max = nums[index]+index > max ? nums[index]+index : max;
        index++;//下一个起始点
    }
    return true;
}

//第一名的解法，更为简洁易懂，从后往前推出来
public boolean canJump(int[] nums) {
    if(nums.length<=1) return true;
    int len=1;
    for(int i=nums.length-2;i>0;i--){
        if(nums[i]<len) len++;
        else{
            len=1;
        }
    }
    return nums[0]>=len;
}

public int[][] merge(int[][] intervals) {
    List<int[]> result = new ArrayList<>(intervals.length);
    if (intervals == null || intervals.length == 0) return new int[0][];
    if (intervals.length == 1) return intervals;

    Arrays.sort(intervals, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return o1[0]-o2[0];
        }
    });

    int start = intervals[0][0], end = intervals[0][1];
    for (int i = 1, len = intervals.length; i < len; i++) {
        if (end >= intervals[i][0]) {
            end = Math.max(intervals[i][1], end);
        } else {
            result.add(new int[]{start, end});
            start = intervals[i][0];
            end = intervals[i][1];
        }
    }
    result.add(new int[]{start, end});

    int[][] rArr = new int[result.size()][2];
    for (int i = 0, len = result.size(); i < len; i++) {
        rArr[i] = result.get(i);
    }
    return rArr;
}

public int uniquePaths(int m, int n) {
    // 这个推导公式比较容易得到
    // dp[i][j] = dp[i-1][j]+dp[i][j-1]
    int[][] dp = new int[m][n];
    for (int j = 0; j < n; j++) {
        dp[0][j] = 1;
    }
    for (int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j]+dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}

public int minPathSum(int[][] grid) {
    int row = grid.length, col = grid[0].length;
    int[][] dp = new int[row][col];

    for (int j = 0; j < col; j++) {
        if (j == 0) dp[0][j] = grid[0][j];
        else dp[0][j] = dp[0][j-1]+grid[0][j];
    }

    for (int i = 0; i < row; i++) {
        if (i == 0) continue;
        dp[i][0] = dp[i-1][0]+grid[i][0];
    }

    for (int i = 1; i < row; i++) {
        for (int j = 1; j < col; j++) {
            dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1])+grid[i][j];
        }
    }

    return dp[row-1][col-1];
}

private int[] f = new int[1024];
public int climbStairs(int n) {
    if(f[n]!=0) return f[n];
    f[0] = 1;
    f[1] = 1;
    f[2] = 2;
    for(int i = 3; i<=n; i++) {
        f[i] = f[i-1]+f[i-2];
    }
    return f[n];
}

public int minDistance(String word1, String word2) {
    if (word1.equals(word2)) return 0;
    if (word1.length() == 0) return word2.length();
    if (word2.length() == 0) return word1.length();

    int col = word1.length(), row = word2.length();
    int[][] dp = new int[col+1][row+1];
    for (int i = 0; i <= col; i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= row; j++) {
        dp[0][j] = j;
    }
    for (int i = 1; i <= col; i++) {
        for (int j = 1; j <= row; j++) {
            if (word1.charAt(i-1) == word2.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = Math.min(dp[i][j-1], Math.min(dp[i-1][j], dp[i-1][j-1]))+1;
            }
        }
    }
    return dp[col][row];
}

public void sortColors(int[] nums) {
    if (nums == null || nums.length <= 1) return;

    int left = 0, right = nums.length-1, i = 0;
    while (left < right && i <= right) {
        if (nums[i] == 2) {
            swap(nums, i, right--);
        } else if (nums[i] == 0) {
            swap(nums, i++, left++);
        } else {
            i++;
        }
    }
}

private void swap(int[] nums, int i, int i1) {
    int temp = nums[i];
    nums[i] = nums[i1];
    nums[i1] = temp;
}

public String minWindow(String s, String t) {
    if(t == null || t.length() == 0) return "";
    if(s.length() < t.length()) return "";
    if(s.equals(t)) return s;

    int len2 = t.length();
    HashMap<Character, Integer> hashMapT = new HashMap<>();
    for(int i = 0; i < len2; i++) {
        hashMapT.put(t.charAt(i), hashMapT.getOrDefault(t.charAt(i), 0)+1);//记录T字符串中每个字符出现的次数
    }

    int len1 = s.length();
    HashMap<Character, Integer> hashMapS = new HashMap<>();
    int start = 0, count = 0;//start记录字符串的起始位置
    String result = "";
    for(int i = 0; i < len1; i++) {
        if(hashMapT.getOrDefault(s.charAt(i), 0) > 0) {//当遇到t中的字符串时，就开始记录判断
            hashMapS.put(s.charAt(i), hashMapS.getOrDefault(s.charAt(i), 0)+1);//同时记录s字符串中包含t中字符的次数记录

            if(hashMapS.get(s.charAt(i)) <= hashMapT.get(s.charAt(i))) {
                count++;
            }

            while(count == len2) {
                if("".equals(result) || result.length() > i-start+1) {
                    result = s.substring(start, i+1);//获得包含t字符的字符串
                }

                //然后将start移动到出现在第一个含有t的字符位置
                if(hashMapT.getOrDefault(s.charAt(start), 0) != 0) {
                    hashMapS.put(s.charAt(start), hashMapS.get(s.charAt(start))-1);
                    if(hashMapS.get(s.charAt(start)) < hashMapT.get(s.charAt(start))) {
                        count--;//移动到第一个出现的位置后
                    }
                }
                start++;
            }
        }
    }
    return result;
}

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();//存储每个组合出来的子集
    if(nums == null || nums.length == 0) return result;
    result.add(new ArrayList<>(0));
    int len = nums.length;
    for(int i=0; i < len; i++) {
        int size = result.size();
        for(int j = 0; j < size; j++) {
            List<Integer> temp = new ArrayList<>(result.get(j));//这一步操作很奇妙，有种动态规划的做法

            temp.add(nums[i]);
            result.add(temp);
        }
    }
    return result;
}

public boolean exist(char[][] board, String word) {
    if (board == null || board.length == 0 || board[0].length == 0) return false;
    if (word == null || word.length() == 0) return true;

    int row = board.length, col = board[0].length;

    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (existHelper(board, word, 0, i, j)) {
                return true;
            }
        }
    }
    return false;
}

private boolean existHelper(char[][] board, String word, int strIndex, int i, int j) {

    if (strIndex >= word.length()) return true;

    if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] != word.charAt(strIndex)) return false;

    board[i][j] = '0';//置为0
    boolean res = existHelper(board, word, strIndex+1, i+1, j) || existHelper(board, word, strIndex+1, i-1, j) || existHelper(board, word, strIndex+1, i, j-1) || existHelper(board, word, strIndex+1, i, j+1);
    board[i][j] = word.charAt(strIndex);
    return res;
}

//暴力搜索法
public int largestRectangleArea(int[] heights) {
    if (heights == null && heights.length == 0) return 0;
    if (heights.length == 1) return heights[0];
    int len = heights.length;

    int maxArea = 0;
    for (int i = 0; i < len; i++) {
        int min = heights[i];
        for (int j = i; j < len; j++) {
            min = Math.min(min, heights[j]);
            maxArea = Math.max(maxArea, min*(j-i+1));
        }
    }

    return maxArea;
}
//第二种方法：参考别人的
public int largestRectangleArea(int[] heights) {
    if (heights == null || heights.length == 0) return 0;
    return getMax(heights, 0, heights.length);
}    
int getMax(int[] heights, int s, int e) {
    if (s + 1 >= e) return heights[s];
    int min = s;
    boolean sorted = true;
    for (int i = s; i < e; i++) {
        if (i > s && heights[i] < heights[i - 1]) sorted = false;
        if (heights[min] > heights[i]) min = i;
    }
    //有序情况的最大值
    if (sorted) {
        int max = 0;
        for (int i = s; i < e; i++) {
            max = Math.max(max, heights[i] * (e - i));
        }
        return max;
    }
    int left = (min > s) ? getMax(heights, s, min) : 0;
    int right = (min < e - 1) ? getMax(heights, min + 1, e) : 0;
    return Math.max(Math.max(left, right), (e - s) * heights[min]);
}

public int maximalRectangle(char[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return 0;
    }
    int m = matrix.length, n = matrix[0].length;
    int result = matrix[0][0] == '1' ? 1 : 0;
    int[] height = new int[n];
    int[] left = new int[n];
    int[] right = new int[n];
    Arrays.fill(right, n);
    for (int i  = 0; i < m; i++) {
        int cur_left = 0, cur_right = n;
        //寻找最左边的边界
        for (int j = 0; j < n; j++) {

            if (matrix[i][j] == '1') {
                height[j]+=1;
                left[j] = Math.max(left[j], cur_left);
            } else {
                height[j] = 0;
                left[j] = 0;//
                cur_left = j+1;
            }
        }
        //寻找最右边的边界
        for (int j = n-1; j >= 0; j--) {
            if (matrix[i][j] == '1') {
                right[j] = Math.min(right[j], cur_right);
            } else {
                right[j] = n;
                cur_right = j;
            }

            result = Math.max(result, (right[j] - left[j])*height[j]);
        }
    }

    return result;
}

//递归方式
public List<Integer> inorderTraversal(TreeNode root) {
    //递归调用方式
    if (root == null) return result;
    if (root.left != null) inorderTraversal(root.left);
    result.add(root.val);
    if (root.right != null) inorderTraversal(root.right);
    return result;
}

//非递归方式
List<Integer> inorderLoop = new ArrayList<>();
Deque<TreeNode> nodeQueue = new ArrayDeque<>();
TreeNode point = root;
while(point!=null || !nodeQueue.isEmpty()) {
    // inorderLoop.add(nodeQueue.pop().val);
    while(point!=null) {
        nodeQueue.push(point);
        point = point.left;
    }
    TreeNode tmp = nodeQueue.pop();
    inorderLoop.add(tmp.val);
    point = tmp.right;
}
return inorderLoop;

public int numTrees(int n) {
    int[] dp = new int[n+1];
    if(n==1) return 1;
    dp[0] = 1;
    dp[1] = 1;
    for(int i = 2; i <= n; i++) {
        for(int j = 1; j <= i; j++) {
            dp[i] += dp[j-1]*dp[i-j];
        }
    }
    return dp[n];
}

public boolean isValidBST(TreeNode root) {
    return isValidHelper(root, null, null);

}

private boolean isValidHelper(TreeNode root, Integer min, Integer max) {
    if (root == null) return true;
    if (max != null && root.val >= max) return false;
    if (min != null && root.val <= min) return false;

    return isValidHelper(root.left, min, root.val) && isValidHelper(root.right, root.val, max);
}

public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    if (root.left == null && root.right == null) return true;
    if (root.left == null || root.right == null) return false;

    return isSymmetric(root.left, root.right);
}

private boolean isSymmetric(TreeNode left, TreeNode right) {
    if (left == null && right == null) return true;
    if (left == null || right == null) return false;

    if (left.val != right.val) return false;

    return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);

}

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    if (root.left == null && root.right == null) return 1;

    return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
}

public TreeNode buildTree(int[] preorder, int[] inorder) {
    return build(preorder, inorder, 0, 0, inorder.length-1);
}

private TreeNode build(int[] preorder, int[] inorder, int preStart, int inStart, int inEnd) {

    if (preStart > preorder.length - 1 || inStart > inEnd) {
        return null;
    }

    TreeNode root = new TreeNode(preorder[preStart]);
    int inRootIndex = inStart;
    while (inRootIndex <= inEnd && inorder[inRootIndex] != preorder[preStart]) inRootIndex++;

    int leftTreeLen = inRootIndex-inStart;//左子树长度

    int preLeftStart = preStart+1;
    int preRightStart = preStart+leftTreeLen+1;

    root.left = build(preorder, inorder, preLeftStart, inStart, inRootIndex-1);
    root.right = build(preorder, inorder, preRightStart, inRootIndex+1, inEnd);

    return root;
}

public boolean isBalanced(TreeNode root) {
    if(root == null) return true;
    if(root.left == null && root.right == null) return true;

    int left = getHeight(root.left);
    int right = getHeight(root.right);

    if (Math.abs(left-right) <= 1) return isBalanced(root.left) && isBalanced(root.right);
    else return false;

}

private int getHeight(TreeNode root) {
    if(root == null) return 0;
    if(root.left == null && root.right == null) return 1;

    return Math.max(getHeight(root.left), getHeight(root.right))+1;
}

public int minDepth(TreeNode root) {
        return getHeight(root);

    }

    private int getHeight(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 1;
        
        int left, right;
        if(root.left == null) left = Integer.MAX_VALUE;
        else left = getHeight(root.left);
        if(root.right == null) right = Integer.MAX_VALUE;
        else right = getHeight(root.right);
        
        return Math.min(left, right)+1;
    }