数组最大单次位移问题求解与代码实现咨询

问题描述 #

支撑设备的杆在风中晃动，其倾斜角度按均匀时间间隔记录为数值序列。例如[-1, 0, 1]表示t=0时左倾1度，t=1时垂直，t=2时右倾1度。

要求编写函数，从序列中找出最大单次位移对应的起始、结束时间点及角度值：

• 输入示例：[1, 0, -1, 2, 3, 1]
• 输出示例：{"t2": -1, "t4": 3}
• 解释：t0-t2位移2度，t2-t4位移4度，t4-t5位移2度，其中t2到t4的4度是最大单次位移。

给定代码框架：

static int[] largestSingleMovement(int arr[]){
    int x = arr.length;
}

解法思路 #

核心是识别连续单向移动的起止点（极值点）：

1. 单次位移指从一个极值点（局部最高/最低）到下一个相反极值点的单向移动过程，位移大小为两点角度差的绝对值。
2. 遍历数组时跳过连续相等的元素（无位移发生），仅当趋势改变时标记为极值点。
3. 计算每对相邻极值点的位移，记录最大位移对应的起止信息。

代码实现 #

这里调整返回类型为Map以匹配示例输出格式，若需用int[]返回，可改为返回{起始索引, 起始角度, 结束索引, 结束角度}的数组：

import java.util.HashMap;
import java.util.Map;

public class RodMovement {
    static Map<String, Integer> largestSingleMovement(int arr[]) {
        Map<String, Integer> result = new HashMap<>();
        int n = arr.length;
        if (n < 2) {
            return result;
        }

        int prevVal = arr[0];
        int prevIdx = 0;
        int maxDisplacement = 0;
        int startIdx = 0;
        int endIdx = 0;

        for (int i = 1; i < n; i++) {
            // 跳过无位移的连续相等值
            if (arr[i] == prevVal) {
                continue;
            }

            // 判断当前是否为极值点（趋势改变或到达数组末尾）
            boolean isExtreme = false;
            if (i == n - 1) {
                isExtreme = true;
            } else {
                boolean prevTrend = (arr[i] - prevVal) > 0;
                boolean nextTrend = (arr[i+1] - arr[i]) > 0;
                isExtreme = prevTrend != nextTrend;
            }

            if (isExtreme) {
                int currentDisplacement = Math.abs(arr[i] - prevVal);
                // 更新最大位移记录
                if (currentDisplacement > maxDisplacement) {
                    maxDisplacement = currentDisplacement;
                    startIdx = prevIdx;
                    endIdx = i;
                }
                prevVal = arr[i];
                prevIdx = i;
            }
        }

        result.put("t" + startIdx, arr[startIdx]);
        result.put("t" + endIdx, arr[endIdx]);
        return result;
    }

    public static void main(String[] args) {
        int[] input = {1, 0, -1, 2, 3, 1};
        System.out.println(largestSingleMovement(input)); // 输出 {t2=-1, t4=3}
    }
}

复杂度分析 #

• 时间复杂度：O(n)，仅需一次遍历数组，所有操作均为常数时间。
• 空间复杂度：O(1)，除结果存储外，仅使用固定数量的临时变量，无额外线性空间开销。

内容的提问来源于stack exchange，提问作者user13734449