You need to enable JavaScript to run this app. Codewars Direction Reduction任务C++解法运行过慢 如何优化性能?
优惠活动
大模型
产品
解决方案
定价
更多

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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.22 08:06:06