[数据结构与算法]华为机试 HJ24 合唱队【java实现】

描述
N 位同学站成一排，音乐老师要请最少的同学出列，使得剩下的 K 位同学排成合唱队形。
通俗来说，能找到一个同学，他的两边的同学身高都依次严格降低的队形就是合唱队形。
例子：
123 124 125 123 121 是一个合唱队形
123 123 124 122不是合唱队形，因为前两名同学身高相等，不符合要求
123 122 121 122不是合唱队形，因为找不到一个同学，他的两侧同学身高递减。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
注意：不允许改变队列元素的先后顺序 且 不要求最高同学左右人数必须相等

找到每个位置的向左递减子序列和向右递减子序列
186 186 150 200 160 130 197 200

向左递减子序列

• 186 左边没有，算上它自己 1

• 186 左边只有186，因此也只算它自己 1

• 150 左边没有比他小的 1

• 200 递减子序列 由于 右边有三个数 150，186，186 这三个最长的递减子序列 为 1，因此 200 的递减子序列为 1 + 1 = 2

• 160，只比150大，因此它的最长递减子序列 为 150的 + 1 也为 2

• 130 右边没有比它小的，因此为 1

• 197 右边比它小的最长子序列为2，因此 为 3

• 200 显然为 4

  即

向右递减子序列

• 200 右边没有 1
• 197 右边没有比它小的 1
• 130 同理 1
• 160 2
• 200 3
• 150 2
• 186 3
• 186 3

即

由于计算递减子序列的时候对拐点处多加一，所以合唱队列为 左子序列 + 右子序列 - 1

package com.wy.leetcode;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author HelloWorld
 * @create 2022/4/20 08:00
 * @email helloworld.dng@gmail.com
 */
public class ChorusSort {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 获取输入的数组长度
        int n = scanner.nextInt();
        ArrayList<Integer> list = new ArrayList<>();
        int i = n;
        while (i-- > 0) {
            list.add(scanner.nextInt());
        }

        System.out.println(doChorusSort(list, n));

    }

    /**
     * @param list int 集合
     * @param n    集合的长度
     * @return int
     * @description 合唱队
     * @author HelloWorld
     * @create 2022/4/22 19:11
     */
    public static int doChorusSort(List<Integer> list, int n) {
        /* 找到每一个位置的向左递减子序列和向右递减子序列的长度*/

        HashSet<Integer> results = new HashSet<>();

        List<Node> leftNodes = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int currentPosition = i;
            Integer currentSize = list.get(i);

            Node node = new Node(currentSize, currentPosition);
            leftNodes.add(node);
            Integer length = null;
            //  当前节点左递减子序列 为它右边值比它小的节点中 最长的节点长度 + 1
            try {
                length = leftNodes.stream()
                        .filter(node1 -> node1.getSize() < currentSize && node1.getPosition() < currentPosition)
                        .max(Comparator.comparing(Node::getLength))
                        .get()
                        .getLength();
            } catch (Exception e) {
                length = 0;
            }
            leftNodes.get(i).setLength(length + 1);
        }
        List<Node> rightNodes = new ArrayList<>();
        for (int i = n - 1; i >= 0 ; i--) {
            int currentPosition = i;
            Integer currentSize = list.get(i);

            Node node = new Node(currentSize, currentPosition);
            rightNodes.add(node);

            Integer length;
            try {
                length = rightNodes.stream()
                        .filter(node1 -> node1.getSize() < currentSize && node1.getPosition() > currentPosition)
                        .max(Comparator.comparing(Node::getLength))
                        .get()
                        .getLength();
            } catch (Exception e) {
                length = 0;
            }

            rightNodes.get(n - 1 -i).setLength(length + 1);
            results.add(leftNodes.get(i).getLength() + rightNodes.get(n - i -1).getLength() - 1);
        }
        
        // 减去最长队列长度得到就是最少出队人数
        return n - results.stream().max(Comparator.comparing(Integer::intValue)).get();

    }

}

class Node {
    private int size;
    private int position;
    private int length;

    public Node(Integer size, Integer position) {
        this.size = size;
        this.position = position;
    }

    public Integer getSize() {
        return size;
    }

    public void setSize(Integer size) {
        this.size = size;
    }

    public Integer getPosition() {
        return position;
    }

    public void setPosition(Integer position) {
        this.position = position;
    }

    public Integer getLength() {
        return length;
    }

    public void setLength(Integer length) {
        this.length = length;
    }
}

阅读世界，共赴山海

423全民读书节，邀你共读