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)，适合处理大规模输入。
➡️
