leetcode 1562. 查找大小为 M 的最新分组-Find Latest Group of Size M

张开发
• 2026/4/16 1:29:45 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

leetcode 1562. 查找大小为 M 的最新分组-Find Latest Group of Size M
Problem: 1562. 查找大小为 M 的最新分组-Find Latest Group of Size M正难则反的递归全是1从arr数组逆向思考每次将长度n分割成两部分初始l1, rn分割以后就是 (l, arr[index]-1), (arr[index]1, r)分割的前提是分割点arr[index]在区间[l, r]范围内所以需要先找到合适的分割点while(index0 (arr[index] l || arr[index] r) ) index–;剪枝若 index ans返回若 r-l target 也返回因后续长度不断缩短肯定不满足要求若l r也返回若r - ltarget记录最大索引Codeclass Solution { public: int target, ans -1; void dfs(vectorint arr, int index, int l, int r) { if(index ans) return; if(r - l target) { ans max(index, ans); return; } else if(r - l target) return; if(l r) return; if(index -1) return; while(index0 (arr[index] l || arr[index] r) ) index--; if(index 0) return; dfs(arr, index - 1, l, arr[index] - 1); dfs(arr, index - 1, arr[index] 1, r); } int findLatestStep(vectorint arr, int m) { int n arr.size(); target m - 1; dfs(arr, n - 1, 1, n); if(ans 0) return ans; else return ans 1; } };

更多文章