Array例题分析（2）

-- Minimum Path Sum ?

    >> 题目：从二维数组中找出从左上角到右下角的最短路径

    >> 解题思路：动态规划

-- Merge Sorted Array 

    >> 题目：将两个数组合并

    >> 解题思路：合并

-- Merge Intervals ?

    

-- Median of Two Sorted Arrays ?

-- Maximum Subarray 
     >> 题目：求子数组的最大和
     >> 解题思路：记录历史值，需要记录两个一个是以i结尾的子数组和的最大值，另一个是i以内的子数组最大值  。每一步都需要更新，注意后者更新需要比较三个数，所以先比较前者。

    public int maxSubArray(int[] A) {
        int []all = new int[A.length];
        int []end = new int[A.length];
        all[0] = A[0];
        end[0] = A[0];
        for (int i = 1; i < A.length; i++) {
            end[i] = Math.max(A[i], end[i - 1] + A[i]);
            all[i] = Math.max(all[i - 1], end[i]); // 其实是需要比较三个数的，但是end已经计算了两个数
        }
        return all[A.length - 1];
    }

-- Maximum Product Subarray  ?

-- Maximal Rectangle?

-- Majority Element ?

-- Longest Consecutive Sequence?

-- Largest Rectangle in Histogram ？

-- Jump Game ？

-- Jump Game II ？

-- Insert Interval ？

-- First Missing Positive 

    >> 题目：从无序数组中找到第一个没有出现的正数，要求试驾复杂度为n，空间为1

    >> 解题思路：排序（类似于桶排序，但是时间复杂度略高）。查找

-- Find Peak Element 

    >> 题目：查找数组中的峰值

    >> 解题思路：遍历，注意边界处理

    public int findPeakElement(int[] num) {
        boolean increase_flag = false;
        if (num.length == 0)
            return -1;
        if (num.length == 1)
            return 0;
        if (num[0] > num[1])
            return 0;
        for (int i = 1; i < num.length; i++) {
            if (num[i] > num[i - 1]) {
                increase_flag = true;
                if (i == num.length - 1)
                    return i;
            }
            if (increase_flag) {
                if (num[i] < num[i - 1])
                    return i - 1;
                else {

                }
            }
        }
        return -1;
    }

-- Find Minimum in Rotated Sorted Array

    >> 题目：在循环右移后的数组中找最小值

    >> 解题思路：二分查找变种

    public int findMin(int[] num) {
        if (num == null || num.length == 0)
            return 0;
        int l = 0;
        int r = num.length - 1;
        int min = num[0];
        while (l < r - 1) {
            int m = (l + r) / 2;
            if (num[l] < num[m]) {
                min = Math.min(num[l], min);
                l = m + 1;
            } else if (num[l] > num[m]) {
                min = Math.min(num[m], min);
                r = m - 1;
            } else {
                l++;
            }
        }
        min = Math.min(num[r], min);
        min = Math.min(num[l], min);
        return min;
    }

-- Container With Most Water  
    >> 题目：在一个坐标系中，给出若干点，每个点做x轴的垂直线，然后求任何两条线形成的容器中能盛下最多水的情况
    >> 解题思路：刚开始看到这道题的时候有点不清楚题目的意思，以为中间部分也是需要计算的。原来是不需要啊，那就简单了

    public int maxArea(int[] height) {
        if (height == null || height.length < 2) {
            return 0;
        }
        int i = 0, j = height.length - 1;
        int max = 0, temp = 0;

        while (i < j) {
            temp = Math.min(height[j], height[i]) * (j - i);
            max = Math.max(temp, max);

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

        }
        return max;
    }