LeetCode最大宽度坡问题：排序解法原理及关键代码疑问

首先来解决你提到的两个基础语法疑问，再深入拆解解法的工作原理：

1. 关于float('inf')的含义 #

float('inf')是Python中表示正无穷大的特殊常量。在这段代码里，我们初始化变量m为正无穷，目的是让第一次遍历索引时，min(m, i)必然会取到第一个索引值（因为任何整数都比正无穷小），这样就能正确开启后续的最小索引追踪。

2. 关于A.__getitem__的作用 #

A.__getitem__是Python列表的内置方法，它的作用就是通过索引获取列表中的元素——比如我们平时写A[i]，本质上就是调用A.__getitem__(i)。

在sorted(range(len(A)), key = A.__getitem__)这行代码里，key参数指定了排序的依据：我们要把range(len(A))生成的所有索引（也就是0到len(A)-1的整数），按照它们在数组A中对应的元素值进行升序排序。举个例子：

• 如果A = [7,2,5,4]，索引0、1、2、3对应的元素分别是7、2、5、4；
• 按元素升序排序后，索引的顺序就变成了1（对应元素2）、3（对应元素4）、2（对应元素5）、0（对应元素7），和你提供的例子完全一致。

3. 排序解法的工作原理拆解 #

我们先回顾坡的定义：坡是满足i < j且A[i] <= A[j]的元组(i,j)，宽度为j-i，我们要找最大的宽度。

这个解法的核心思路是换个角度思考：对于每个元素A[j]，如果能找到最左边的i（也就是最小的i）满足A[i] <= A[j]，那么j-i就是这个j能贡献的最大坡宽。那怎么高效找到所有j对应的最小合法i呢？

排序的操作帮我们做了关键的一步：把所有索引按A[i]的升序排列后，排在前面的索引对应的A值，一定小于等于排在后面的索引对应的A值。也就是说，在这个排序后的索引序列里，任意两个前面的索引m和后面的索引i，都满足A[m] <= A[i]——这刚好符合坡的A[i] <= A[j]条件！

接下来遍历这个排序后的索引序列时，我们只需要做两件事：

• 维护一个变量m，记录遍历过的所有索引中最小的那个（因为最小的m和当前i的差值i-m最大）；
• 维护一个变量ans，记录遍历过程中出现的最大i-m值。

用你提供的例子A = [7,2,5,4]走一遍流程：

1. 排序后的索引序列是[1,3,2,0]，初始化ans=0，m=inf；
2. 第一个索引是1：ans = max(0, 1 - inf) = 0，m = min(inf, 1) = 1；
3. 第二个索引是3：ans = max(0, 3-1) = 2，m保持1；
4. 第三个索引是2：ans = max(2, 2-1) = 2，m保持1；
5. 第四个索引是0：ans = max(2, 0-1) = 2，m = min(1, 0) = 0；
6. 最终返回ans=2，也就是最大坡宽，和实际情况一致（比如坡(1,3)宽度为2）。

这种方法的巧妙之处在于，通过排序把“寻找满足A[i]<=A[j]的i”的问题转化为“追踪最小索引”的问题，时间复杂度主要由排序决定，是O(n log n)，比暴力枚举的O(n²)高效很多。

内容的提问来源于stack exchange，提问作者user12852585