1. 问题理解与定义
给定一个整数数组A，坡是元组(i, j)，其中i < j且A[i] <= A[j]。这样的坡的宽度为j - i。我们需要在A中找到最大宽度的坡。如果不存在，返回0。
示例1： 输入：[6,0,8,2,1,5] 输出：4 解释：最大宽度的坡出现在(i,j)=(1,5): A[1]=0且A[5]=5且0<=5
示例2： 输入：[9,8,1,0,1,9,4,0,4,1] 输出：7 解释：最大宽度的坡出现在(i,j)=(2,9): A[2]=1且A[9]=1且1<=1
2. 暴力解法分析
最直观的解法是双重循环遍历所有可能的(i,j)对：
int maxWidthRamp(int* A, int ASize) { int max_width = 0; for (int i = 0; i < ASize; i++) { for (int j = i + 1; j < ASize; j++) { if (A[i] <= A[j]) { max_width = fmax(max_width, j - i); } } } return max_width; }时间复杂度：O(n²) 空间复杂度：O(1)
虽然简单直观，但对于大规模数据(如n=50000)会超时，需要优化。
3. 优化思路：单调栈
观察到坡的起点i需要满足：A[i]是某个递减序列的最小值。我们可以使用单调栈来记录这些候选起点。
3.1 构建单调递减栈
int* buildDecreasingStack(int* A, int ASize, int* stackSize) { int* stack = malloc(ASize * sizeof(int)); *stackSize = 0; for (int i = 0; i < ASize; i++) { if (*stackSize == 0 || A[i] < A[stack[*stackSize - 1]]) { stack[(*stackSize)++] = i; } } return stack; }3.2 从后向前遍历找最大宽度
int findMaxWidth(int* A, int ASize, int* stack, int stackSize) { int max_width = 0; for (int j = ASize - 1; j >= 0; j--) { while (stackSize > 0 && A[stack[stackSize - 1]] <= A[j]) { max_width = fmax(max_width, j - stack[stackSize - 1]); stackSize--; } } return max_width; }3.3 完整实现
int maxWidthRamp(int* A, int ASize) { int stackSize; int* stack = buildDecreasingStack(A, ASize, &stackSize); int max_width = findMaxWidth(A, ASize, stack, stackSize); free(stack); return max_width; }时间复杂度：O(n) 空间复杂度：O(n)
4. 算法正确性证明
- 单调栈保证了我们只考虑可能的候选起点i
- 从后向前遍历确保找到每个i对应的最远j
- 当A[stack.top] <= A[j]时，j是当前i能到达的最远位置
5. 边界情况处理
- 空数组或单元素数组：直接返回0
- 完全递减数组：返回0
- 完全递增数组：返回n-1
6. 复杂度分析
构建单调栈：O(n) 查找最大宽度：O(n) 总体：O(n)
7. 测试用例
void test() { int case1[] = {6,0,8,2,1,5}; assert(maxWidthRamp(case1, 6) == 4); int case2[] = {9,8,1,0,1,9,4,0,4,1}; assert(maxWidthRamp(case2, 10) == 7); int case3[] = {1,1,1,1}; assert(maxWidthRamp(case3, 4) == 3); int case4[] = {5,4,3,2,1}; assert(maxWidthRamp(case4, 5) == 0); printf("All test cases passed.\n"); }8. 优化技巧
- 可以合并两个步骤到一个循环中，减少内存分配
- 使用指针操作代替数组索引可能更快
- 对于特定数据分布可能有更优解法
9. 实际应用场景
这种算法可以应用于：
- 股票分析（寻找最大价格上升区间）
- 信号处理（寻找满足条件的最大时间窗口）
- 数据流分析（监控满足条件的最大间隔）
10. 扩展思考
- 如果要求i < j且A[i] < A[j]（严格小于），如何修改？
- 如果数组非常大（无法放入内存），如何解决？
- 如果要求同时满足多个条件（如A[i] <= A[j]且B[i] >= B[j]），如何扩展？
提示：在实际编码面试中，建议先提出暴力解法，然后逐步优化，解释每一步的思考过程。
