DEV Community
·
962. 最大坡度宽度
💡
原文英文，约600词，阅读约需3分钟。
📝
内容提要
文章介绍了如何在整数数组中找到最大坡度宽度。坡度是指一对索引 (i, j)，满足 i < j 且 nums[i] <= nums[j]，宽度为 j - i。解决方案使用单调递减栈，先构建栈保持索引递减，再从数组末尾遍历寻找最大宽度。时间复杂度为 O(n)，适合大规模输入。示例中，数组 [6, 0, 8, 2, 1, 5] 的最大坡度宽度为 4。
🎯
关键要点
-
坡度是指一对索引 (i, j)，满足 i < j 且 nums[i] <= nums[j]，宽度为 j - i。
-
给定整数数组 nums，返回 nums 中的最大坡度宽度，如果没有坡度，返回 0。
-
示例 1 中，数组 [6, 0, 8, 2, 1, 5] 的最大坡度宽度为 4。
-
示例 2 中，数组 [9, 8, 1, 0, 1, 9, 4, 0, 4, 1] 的最大坡度宽度为 7。
-
解决方案使用单调递减栈，保持索引递减，便于后续查找满足条件的 (i, j) 对。
-
从数组末尾遍历，寻找每个 j 对应的最远 i，计算宽度并更新最大宽度。
-
时间复杂度为 O(n)，适合处理大规模输入。
❓
延伸问答
如何定义数组中的坡度宽度？
坡度宽度是指一对索引 (i, j)，满足 i < j 且 nums[i] <= nums[j]，宽度为 j - i。
如何找到给定数组的最大坡度宽度？
可以使用单调递减栈，先构建栈保持索引递减，然后从数组末尾遍历寻找最大宽度。
给定数组 [6, 0, 8, 2, 1, 5] 的最大坡度宽度是多少？
最大坡度宽度为 4，对应的索引对为 (1, 5)。
时间复杂度是多少，适合处理多大规模的输入？
时间复杂度为 O(n)，适合处理最大长度为 5 * 10^4 的输入。
如何使用单调递减栈来解决这个问题？
通过维护一个递减的索引栈，遍历数组时可以快速找到满足条件的 (i, j) 对。
如果数组中没有坡度，应该返回什么？
如果没有坡度，应该返回 0。
➡️
