求数组中最长单调不降连续子数组的长度
1、题目描述
多多君正在研究字符串数组的单调性。他定义一个字符串数组为单调不降当且仅当对所有相邻元素s[i] 和s[i+1]，都有s[i]≤s[i+1]，其中≤表示：
1.首先按照字符串的长度比较，长度更长的字符串更大，如 banana > apple
2.在长度相等的情况下，按字符串的字典序比较，字典序较大的字符串更大，如 chery > banana
给定苦干组测试数据，每组数据包含一个字符串数组。你需要计算该数组中最长的单调不降连续子数组的长度。
输入描述：
第一行为一个整数T(1<=T<=1000)，表示测试用例的数量。
接下俩的2T行，每两行表示一组测试用例：
第一行为当前测试用例输入的字符串数组的长度n(1<=n<=1000)
第二行为n个由空格分隔的字符串，对应字符串数组中的每个元素；其中每个字符串仅包含小写字母，长度不超过20.
输出描述：
输出包含T行
每一行为对应测试用例中，最长的单调不降连续子数组的长度
补充说明：
20%数据满足n<=100
50%数据满足n<=500
100%数据满足n<=1000
长度为1的字符串数组也可以单调不降
实例1
输入：
2
3
apple banana cherry
4
dog cat bird elephant
输出：
3
3
说明：
第一组数据中，apple<banana<cherry，所以结果为3
第二组数据中，dog>cat， cat<bird，bird<elephant，所以结果为3
2、解题思路
要解决这个问题，我们需要找到字符串数组中最长的单调不降连续子数组的长度。单调不降的定义是：对于所有相邻的字符串，前一个字符串的长度小于或等于后一个字符串的长度，如果长度相等，则前一个字符串的字典序小于或等于后一个字符串的字典序。
方法思路
-
输入处理：首先读取测试用例的数量T，然后逐个处理每个测试用例。对于每个测试用例，读取字符串数组的长度n和字符串数组本身。
-
单调性检查：对于每个字符串数组，我们需要检查每个相邻字符串是否满足单调不降的条件。具体来说，对于相邻的字符串s[i]和s[i+1]，需要满足s[i]的长度小于s[i+1]的长度，或者长度相等时s[i]的字典序小于等于s[i+1]的字典序。
-
最长子数组计算：使用动态规划的方法来记录以每个位置结尾的最长单调不降子数组的长度。初始化时，每个位置的最长子数组长度为1。然后，对于每个位置i，检查其与前一个位置i-1是否满足单调不降的条件。如果满足，则当前最长子数组长度为前一个位置的最长子数组长度加1；否则，重置为1。最终，最大的长度即为答案。
代码实现
public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int T = scanner.nextInt();scanner.nextLine(); for (int t = 0; t < T; t++) {int n = scanner.nextInt();scanner.nextLine(); String[] strs = scanner.nextLine().split(" ");if (n == 0) {System.out.println(0);continue;}int maxLen = 1;int currentLen = 1;for (int i = 1; i < n; i++) {String prev = strs[i - 1];String curr = strs[i];if (compare(prev, curr) <= 0) {currentLen++;maxLen = Math.max(maxLen, currentLen);} else {currentLen = 1;}}System.out.println(maxLen);}scanner.close();}代码解释
-
输入处理：使用
Scanner读取输入的测试用例数量T，然后逐个处理每个测试用例。对于每个测试用例，读取字符串数组的长度n和字符串数组本身。 -
单调性检查：
compare方法用于比较两个字符串的大小。首先比较字符串的长度，如果长度不同，返回长度的比较结果；如果长度相同，返回字典序的比较结果。 -
最长子数组计算：初始化
maxLen和currentLen为1。遍历字符串数组，对于每个位置i，比较strs[i-1]和strs[i]。如果满足单调不降的条件，增加currentLen并更新maxLen；否则，重置currentLen为1。最终，maxLen即为最长的单调不降连续子数组的长度。