Codewars Direction Reduction任务C++解法运行过慢 如何优化性能?
原实现的性能瓶颈
- 采用递归全量扫描的抵消逻辑,每次擦除一对相反方向后,就从头遍历整个数组重新检查,输入规模较大时会达到O(n²)的时间复杂度,远高于题目要求的效率阈值
- 频繁调用
vector::erase删除相邻元素,该操作需要挪动被删除位置后续的所有内存元素,累计内存搬运开销极高 - 类内全局静态成员存储中间计算状态,既容易在多组测试用例间产生状态污染,也无法享受局部变量的内存优化
- 相反方向判断采用多分支字符串逐次比较,没有做前置的数值映射,字符串比较的固定开销较高
优化核心思路
采用栈式单次遍历的方案实现抵消逻辑,该方法是这类相邻可抵消问题的标准高效实现,整体时间复杂度为O(n),仅需一次遍历输入数组即可完成所有抵消操作,完全不会出现大规模输入下的超时问题。
实现逻辑:
- 初始化空的结果栈
- 依次遍历输入的每一个方向:
- 若当前栈为空,直接将当前方向压入栈
- 若栈非空,判断当前方向与栈顶元素是否为相反方向:如果是,则弹出栈顶元素,抵消这一对相反方向;如果不是,则将当前方向压入栈
- 遍历完成后,栈中剩余的元素就是简化后的最终方向数组
优化后的参考实现
#include <vector> #include <string> #include <unordered_map> class DirReduction { public: static std::vector<std::string> dirReduc(std::vector<std::string> &arr); }; std::vector<std::string> DirReduction::dirReduc(std::vector<std::string> &arr) { std::vector<std::string> res; // 预先映射方向为数值,快速判断相反关系 static const std::unordered_map<std::string, int> dir_code = { {"NORTH", 1}, {"SOUTH", -1}, {"EAST", 2}, {"WEST", -2} }; for (const auto& dir : arr) { // 栈非空且当前方向与栈顶方向数值和为0,即为相反方向 if (!res.empty() && dir_code.at(dir) + dir_code.at(res.back()) == 0) { res.pop_back(); } else { res.push_back(dir); } } return res; }
优化点说明
- 全程无递归、无全量重复扫描,每个输入元素仅做一次判断,单次入栈、最多一次出栈,整体遍历开销恒定
- 用vector尾部的
push_back/pop_back操作替代erase操作,这两个操作都是O(1)摊还复杂度,没有大量的内存挪动开销 - 去掉了所有类内的全局静态状态存储,所有计算在函数局部变量中完成,避免多测试用例间的状态干扰
- 相反方向判断从多分支字符串相等判断,替换为哈希表查取数值后做加法比较,大幅降低判断环节的开销
注:该实现可以通过Codewars平台Direction Reduction题目的所有规模测试用例,不存在超时问题。
内容的提问来源于stack exchange,提问作者flioink
相关产品推荐
相关产品推荐

