引言：递归处理列表与条件性元素移除
在数据处理中，我们经常会遇到需要对列表进行迭代检查和修改的场景。例如，一个常见的需求是：检查一个整数列表是否已排序，如果未排序且列表中的最大值恰好位于列表的起始或末尾，则移除该最大值，并重复此过程，直到列表变得有序或者最大值不再位于两端。这种需要根据当前列表状态（是否排序、最大值位置）进行决策并可能重复操作的问题，非常适合使用递归方法来解决。递归能够优雅地处理这种“重复执行相同逻辑直到满足某个条件”的模式。
初始尝试的问题分析
在深入探讨有效的递归解决方案之前，我们先审视一种常见的初步尝试，并指出其可能存在的逻辑缺陷。例如，以下代码片段展示了一个尝试解决此类问题的初始思路：
public class Solution {
// ... main 方法省略 ...
public static boolean find132pattern(List list) {
int count = 0;
String result = ""; // 字符串用于存储排序结果
for(int i = 0; i < list.size(); i++){
int prev = i-1;
int next = list.get(i);
if(prev > -1){
prev = list.get(i-1);
if(prev > next){
count+=1; // 统计逆序对
}
}
}
if(count > 0){
result+="not sorted";
}else {
result+="sorted";
}
Integer start = 0;
Integer end = list.size(); // 这里的end是列表大小，而非最后一个元素的索引
Integer maxNum = Collections.max(list);
Integer maxPos = list.indexOf(maxNum);
// 逻辑判断和递归调用
if(result == "sorted"){ // 字符串比较应使用 .equals()
return false;
}else if(result == "not sorted" && (maxPos == end || maxPos == start)){ // maxPos == end 存在索引越界风险
list.remove(maxPos);
find132pattern(list); // 递归调用未处理返回值
}else {
System.out.println(list);
}
return false; // 最终总是返回false
}
} 上述代码存在以下几个主要问题：
- 字符串比较错误： 在Java中，String 对象的比较应该使用 .equals() 方法，而非 == 运算符。== 比较的是对象的引用地址，而不是其内容。
- 索引越界风险： end 变量被赋值为 list.size()。当判断 maxPos == end 时，实际上是在检查最大值是否在列表末尾的 下一个位置，这在逻辑上是错误的，并且 list.remove(end) 会导致 IndexOutOfBoundsException。正确的末尾索引应该是 list.size() - 1。
- 递归调用不完整： find132pattern(list) 的递归调用没有使用其返回值。由于该方法最终总是返回 false，这样的递归调用无法有效地传递处理结果或状态。
- 业务逻辑不清晰： 整个方法的返回类型是 boolean，但其主要目的是修改列表。这种不匹配可能导致混淆。
这些问题表明，我们需要一个更严谨、更符合Java编程规范且逻辑更清晰的递归方案。
立即学习“Java免费学习笔记（深入）”；
核心递归策略：查找并移除列表中最大元素
在处理列表时，递归的一个常见应用是遍历列表并根据条件进行操作。以下是一个通用的递归方法，用于在列表中查找并移除 单个 最大元素。这个方法通过一次递归遍历来找到最大元素的索引，然后在遍历结束后进行移除。
import java.util.List;
import java.util.Collections;
import java.util.ArrayList;
public class ListProcessor {
/**
* 递归地从列表中移除最大的元素。
* 该方法通过一次遍历找到最大元素的索引，然后在递归结束时执行移除操作。
*
* @param list 待处理的整数列表。
* @param currentIndex 当前递归遍历到的索引。
* @param maxElementIndexFoundSoFar 迄今为止发现的最大元素的索引。
* @return 移除了最大元素后的列表。
*/
public static List removeBiggestFromListRecursive(List list, int currentIndex, int maxElementIndexFoundSoFar) {
// 基本情况：如果当前索引超出了列表范围，说明已经遍历完整个列表
if (currentIndex >= list.size()) {
// 如果列表不为空，则移除在遍历过程中找到的最大元素
if (!list.isEmpty()) {
list.remove(maxElementIndexFoundSoFar);
}
return list; // 返回修改后的列表
}
else {
// 递归步骤：
// 比较当前元素与迄今为止找到的最大元素
if (list.get(currentIndex) > list.get(maxElementIndexFoundSoFar)) {
// 如果当前元素更大，则更新最大元素的索引
maxElementIndexFoundSoFar = currentIndex;
}
// 递归调用自身，处理下一个元素
return removeBiggestFromListRecursive(list, currentIndex + 1, maxElementIndexFoundSoFar);
}
}
public static void main(String[] args) {
List myList = new ArrayList<>();
myList.add(9);
myList.add(2);
myList.add(3);
myList.add(4);
myList.add(5);
myList.add(22);
System.out.println("原始列表: " + myList); // 输出: [9, 2, 3, 4, 5, 22]
// 调用递归方法移除最大元素
// 初始调用时，currentIndex从0开始，maxElementIndexFoundSoFar也从0开始（假设列表不为空）
if (!myList.isEmpty()) {
myList = removeBiggestFromListRecursive(myList, 0, 0);
}
System.out.println("移除最大元素后的列表: " + myList); // 输出: [9, 2, 3, 4 
