【力扣题解】6091. 划分数组使最大差为 K

😊博主目前也在学习，有错误欢迎指正😊
🌈保持热爱 奔赴星海🌈

文章目录

• • 一、题目
  • • 1、题目描述
    • 2、基础框架
    • 3、原题链接
  • 二、解题报告
  • • 1、思路分析
    • 2、代码详解
  • 三、本题知识

一、题目

1、题目描述

给你一个整数数组 nums 和一个整数 k 。你可以将 nums 划分成一个或多个 子序列 ，使 nums 中的每个元素都 恰好 出现在一个子序列中。
在满足每个子序列中最大值和最小值之间的差值最多为 k 的前提下，返回需要划分的 最少 子序列数目。
子序列 本质是一个序列，可以通过删除另一个序列中的某些元素（或者不删除）但不改变剩下元素的顺序得到。

2、基础框架

• Java版本框架代码如下：

class Solution {    public int partitionArray(int[] nums, int k) {    }}

3、原题链接

6091. 划分数组使最大差为 K

二、解题报告

1、思路分析

       (1)先对nums数组排序，定义两个指针，两个指针在初始时都指向第一个元素，遍历nums数组，若nums[right]和nums[left]的差值小于等于k，右指针右移，若差值大于k，则在指针left和指针right之间的数组就是一个子序列。
       (2)将左右指针移动到子序列的右边，继续查找下一个子序列。最后的结果为res的值。

2、代码详解

class Solution {    public int partitionArray(int[] nums, int k) { Arrays.sort(nums); int res = 0; int left = 0; int right = 0; while(right < nums.length) {     if(nums[right] - nums[left] <= k) {  right++;     }else {  res++;  left = right;  right = left;     } } return res + 1;    }}

三、本题知识

排序+双指针