leetcode594. 最长和谐子序列

leetcode594. 最长和谐子序列

思路

1. 标准的滑动窗口，只求数量，没有顺序，不求序列。那么就进行排序，
2. 自己写的很垃圾，左窗口和右窗口，维护一个最大值最小值更新，用于去掉全相等，不用看
3. 答案里面只用了左右指针，因为排序后，值都是挨在一起的，只用左右指针就可以，判断左右指针是否相等

int cmp(const void *a, const void *b) {
   int c = *((int*)a);
   int d = *((int*)b);
   return c - d; 
}
int findLHS(int* nums, int numsSize){
   qsort(nums, numsSize, sizeof(int), cmp);
   int max_l = 0;
   int count = 0;
   int left = 0;
   int right = left;
   while (right < numsSize) {
       count = right - left;
       while (right < numsSize && nums[right] - nums[left] <= 1 ) {
           count ++ ;
           right ++;
       }
       if (nums[left] == nums[right-1]) {
           count = 0;
       }
       max_l = max(count, max_l);
       while (left <= right && right < numsSize && nums[right] - nums [left] > 1 ) {
           left ++;
       }
   }
   return max_l;
}

int max(int a, int b) {
    if (a > b) {
        return a;
    }
    return b;
}
int min(int a, int b) {
    if (a > b) {
        return b;
    }
    return a;
}

int cmp(const void *a, const void *b) {
    int c = *((int*)a);
    int d = *((int*)b);
    return c - d; 
}
int findLHS(int* nums, int numsSize){
    qsort(nums, numsSize, sizeof(int), cmp);
    int min_v = nums[0];
    int max_v = nums[0];
    int max_l = 0;
    int count = 0;
    int left = 0;
    int right = left;
    while (right < numsSize) {
        count = right - left;
        while (max_v == min_v && right < numsSize && abs(nums[right] - min_v) <= 1 ) {
            max_v = max(max_v, nums[right]);
            min_v = min(min_v, nums[right]);
            count ++ ;
            right ++;
        }
        while (max_v != min_v && right < numsSize) {
            if (max_v >= nums[right] && nums[right] >= min_v) {
                    count ++;
                    right ++;
                }
            else  break;
        }
        if (min_v == max_v) {
            count = 0;
        }
        max_l = max(count, max_l);
        while (left <= right && right < numsSize && nums[right] - nums [left] > 1 ) {
            left ++;
        }
        if (left < numsSize && right < numsSize ) {
            if (nums[left] - nums[right] <= 1) {
                min_v = nums[left];
                max_v = nums[right];
            }
        }
    }
    return max_l;
}

int main () {
    int nums[31] = {2,2,2,2,2,2,2,3,1,0,0,0,3,1,-1,0,1,1,0,0,1,1,2,2,2,0,1,2,2,3,2};
    int res = findLHS(nums, 31); 
    printf("res = %dn", res);

}