网易2021java岗笔试题2

最长震荡子数组：
给定一个数组，如果连续两次递增（或递减）后再两次递减（或递增），允许最开始的时候只有一次递增（或递减），允许最后的时候只有一次递增（或递减）**
解答：
通过设置状态来记录之前的情况。可以分为一下几种情况是合理的：
前前状态 前状态 当前状态
1 NULL NULL INCR/DECR
2 NULL INCR/DECR INCR/DECR
3 INCR INCR DECR
4 INCR DECR DECR
5 DECR DECR INCR
6 DECR INCR INCR

定义枚举用于表示这几种状态：

private static enum Trend {
        INCR(1),
        DECR(-1),
        EQUAL(0),
        NULL(0),
        ;
        public final int score;

        Trend(int score){
            this.score = score;
        }
    }

定义一个函数用于计算当前下标对应的状态：

private static Trend calculateTrend(int[] input, int i) {
        if(i == 0){
            return Trend.NULL;
        }
        int pre = input[i - 1];
        int current = input[i];
        if(current == pre) {
            return Trend.EQUAL;
        }
        if(current > pre) {
            return Trend.INCR;
        } else  {
            return Trend.DECR;
        }
    }

判断当前状态是否合理：

private static boolean canContinue(Trend[] history, Trend current){
        if(current == Trend.EQUAL){
            // 不能与后面连起来了，需要中断计数
            return false;
        }
        if(history[0] == Trend.NULL){
            if(history[1] == Trend.NULL){
                return true;
            }
            // 必須連續
            return history[1] == current;
        }
        if(history[0] == history[1]){
            return current != history[1];
        }
        return current == history[1];
    }

生成历史状态，即把状态逐一推进：

private static  void regenHistoryTrend(Trend[] historyTrend, Trend currentTrend) {
        // 已经连续两个了，只按照时间，推进
        historyTrend[0] = historyTrend[1];
        historyTrend[1] = currentTrend;
    }

主函数：

public class T2 {
    public static void main(String[] args) {
        int[] input = new int[]{1, 2, 3, 2, 1};
        int maxLength = 0;

        for (int i = 0; i < input.length; i++) {
            //以下标i为子数组起点，起始的前两个状态为NULL,NULL
            Trend[] historyTrend = new Trend[]{Trend.NULL, Trend.NULL};

            int score = 0;
            int j = i;
            //从下标i开始遍历数组，用下标j来表示当前的位置
            for (; j < input.length; j++) {
                //计算出下标j所在的状态
                Trend currentTrend = calculateTrend(input, j);
                if(j == i){
                    currentTrend = Trend.NULL;
                }
                score += currentTrend.score;
                // 如果当前状态不符合或者score>2或者score<-2，就退出循环
                if(!canContinue(historyTrend, currentTrend) || score > 2 || score < -2){
                    // 不算本次
                    j --;
                    break;
                }
                regenHistoryTrend(historyTrend, currentTrend);
            }
            int currentLength = j - i;
            if(currentLength >= 5 && currentLength > maxLength){
                maxLength = currentLength;
            }
        }
        System.out.println(maxLength);
    }
}