1. 最连续递增序列（LC 674）

最连续递增序列

题目描述

解题思路

贪心+双指针

固定i指针，让j指针向后走，直到不递增，统计i,j之间的长度，返回最大值

代码实现

public int findLengthOfLCIS(int[] nums) {
        int n = nums.length;
        int ret = 0;
        for(int i = 0;i<n;){
            int j = i+1;
            while(j<n && nums[j-1]<nums[j])
                j++;
            ret = Math.max(ret,j-i);
            i = j;
        }
        return ret;
    }

2. 买卖股票的最佳时机I（LC 121）

买卖股票的最佳时机I

题目描述

解题思路

1. 从1开始固定卖出点，定义一个变量buy作为已经遍历的数中最小买入点
2. 每次统计卖出点与最小买入点的差值，记录最大值。同时更新最小值

代码实现

public int maxProfit(int[] p) {
        int ret = 0;
        int n = p.length;
        int buy = p[0];
        for(int i = 1;i<n;i++){
            ret = Math.max(ret,p[i]-buy);
            buy = Math.min(buy,p[i]);
        }
        return ret;
    }

3. 买卖股票的最佳时机II（LC 122）

买卖股票的最佳时机II

题目描述

解题思路

由于没有交易次数限制，只需要在价格上升的时候卖出，再买入当天的，统计收益

代码实现

public int maxProfit(int[] p) {
        int ret = 0;
        int n = p.length;
        for(int i = 1;i<n;i++){
            if(p[i]>p[i-1])
                ret+=p[i]-p[i-1];
        }
        return ret;
    }

4. K次取反后最大化的数组和（LC 1005）

K次取反后最大化的数组和

题目描述

解题思路

利用大根堆，每次把最小的数填上负号

代码实现

public int largestSumAfterKNegations(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int n = nums.length;
        int sum = 0;

        for(int a:nums){
            sum+=a;
            heap.offer(a);
        }

        while(k>0){
            int a = heap.poll();
            sum-=a*2;
            heap.offer(-a);
            k--;
        }
        return sum;
    }

5. 按身高排序（LC 2418）

按身高排序

题目描述

解题思路

需要记录姓名与身高的映射关系，再对身高进行排序

1. 方法一：利用二元组pair<int,String>,对这个数组排序
2. 方法二：利用hashMap记录身高与名字的映射关系，根据身高排序

以上两种方法空间开销很大

3. 方法三：对下标排序
   1. 创建一个下标数组
   2. 对下标数组排序
   3. 根据排序结果找到原数组的信息

注意： 对于Arrays.sort()的比较函数

1. 只有引用类型数组才支持泛型的 Comparator 重载。int[]是基本类型数组，int[][]是引用类型数组.
2. 这个题的数组是基本类型数组，应该定义成Integer，才可以作为参数传入sort()中

代码实现

public String[] sortPeople(String[] names, int[] heights) {
        int n = names.length;
        Integer[] index = new Integer[n];
        for(int i=0;i<n;i++)
            index[i] = i;

        //根据身高排序
        Arrays.sort(index,(a,b)->heights[b]-heights[a]);
        String[] ret = new String[n];
        for(int i=0;i<n;i++)
            ret[i] = names[index[i]];
        return ret;
    }

6. 优势洗牌（LC 870）

优势洗牌

题目描述

解题思路

田忌赛马

参照田忌赛马的思路，先分别对两个数组排序，如果nums1<nums2，就让nums1[i]去匹配nums[2]最大的数，否则就与当前数匹配

最终返回的结果应该是与是未排序的nums[2]匹配，因此需要先记录nums[2]，对其下标排序

1. 定义left指向index的左端点，表示未排序的最小值；right指向index的右端点，表示未排序的最大值
2. 遍历nums1，与index[left]对应的nums2中的数，也就是nums2[index[left]]
   • 如果优势，就让填写在ret数组，index[left]对应的下标中，也就是ret[index[left]，left后移
   • 如果劣势，就填写在在ret数组，index[right]对应的下标中，也就是ret[index[right]]，right左移

代码实现

public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        Integer[] index  = new Integer[n];
        for(int i = 0;i<n;i++)
            index[i] = i;
        Arrays.sort(nums1);
        Arrays.sort(index,(a,b)->nums2[a]-nums2[b]);

        int left = 0;
        int right = n-1;
        int[] ret = new int[n];

        for(int i = 0;i<n;i++){
            if(nums1[i]>nums2[index[left]]){
                ret[index[left]] = nums1[i];
                left++;
            }else{
                ret[index[right]] = nums1[i];
                right--;
            }
        }
        return ret;
    }