量化 OA 面试真题解析：DirReduc（字符串数组方向抵消）

Write a function dirReduc that takes an array of strings and returns a string array. The returned array should have all unnecessary directions removed, where adjacent opposite directions cancel each other out (NORTH <-> SOUTH and EAST <-> WEST).

Example 1:

Input: ["NORTH", "SOUTH", "EAST", "WEST"]
Output: []

Example 2:

Input: ["NORTH", "EAST", "WEST", "SOUTH", "WEST", "WEST"]
Output: ["WEST", "WEST"]

Note: Not every path can be reduced. For example, [“NORTH”, “WEST”, “SOUTH”, “EAST”] cannot be fully reduced because the remaining directions are not adjacent opposites.

这道题考察的是栈的经典“相邻抵消”模型：把方向数组按顺序遍历，遇到当前方向与栈顶方向互为相反方向时就弹出栈顶，否则将当前方向入栈。这样可以持续消去相邻的 NORTH/SOUTH 与 EAST/WEST 配对，最终栈中剩下的就是无法继续简化的路径。题目重点在于只做相邻抵消，而不是统计全局次数，因此用栈比直接计数更准确，时间复杂度为 O(n)。