上海-思格新能源-一面-技术面

自我介绍
实习的时候有什么样的收获，遇到什么样的问题，如何解决的？
在 Java 中 synchronized 和 Lock 有什么区别？
ThreadLocal 造成内存泄露的原因，怎么解决？
ReentrantLock 在公平锁和非公平锁实现上有什么区别？
什么是线程饥饿？什么场景会造成？怎么样解决？
场景实现分布式锁的工具都有哪些？Redis 实现的分布式锁有什么问题？
消息队列，RabbitMQ 消息生产消费的整个过程？
消息队列消息的幂等性如何保证？
生产者如何确定消息成功发送到服务器呢？
MySQL 可重复读隔离级别能否解决幻读问题？加间隙锁能完全解决幻读问题吗？分页情况下能否问题
哪些情况下不能使用索引？
Spring Bean的完整生命周期

n 个学生围坐成一圈（首尾相邻），老师需要根据每个学生的表现评分（整数数组 scores）分发零食，规则如下：
* 每个学生至少能得到 1 份零食。
* 相邻的两个学生中，评分更高的学生必须得到更多的零食；若评分相同，则两人得到的零食数量必须相等。
* 请计算老师最少需要准备多少份零食。以下是几组 “分发零食” 问题的样例数据：
* 输入：scores = [1, 2, 3]
* 答案：
* 输入：scores = [2, 2, 3]
* 答案：
* 输入：scores = [5, 5, 5, 5]
* 答案：
* 输入：scores = [4, 3, 2, 1]
* 答案：
* 输入：scores = [3, 1, 2, 2, 4]
* 答案：
* 输入：scores = [2, 1, 3, 3]
* 答案：
* 输入：scores = [1, 3, 2, 4]
* 答案：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MinCandiesDistribution {

    /**
     * 计算环形排列学生所需的最少零食数量
     * @param scores 学生评分数组（环形，首尾相邻）
     * @return 最少零食总数
     */
    public static int minCandies(int[] scores) {
        int n = scores.length;
        // 边界处理：无学生或1个学生的情况
        if (n == 0) return 0;
        if (n == 1) return 1;

        // 1. 找到所有评分最小值的索引（作为起始点，最小值应只拿1份零食）
        int minScore = scores[0];
        for (int score : scores) {
            if (score < minScore) {
                minScore = score;
            }
        }
        List<Integer> minIndices = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (scores[i] == minScore) {
                minIndices.add(i);
            }
        }

        int minTotal = Integer.MAX_VALUE; // 存储最终最少零食总数

        // 2. 尝试以每个最小值索引为起点，计算总零食数，取最小值
        for (int start : minIndices) {
            // 2.1 顺时针遍历（从起点向右）：确保当前学生 >= 左侧学生（按规则）
            int[] candiesClockwise = new int[n];
            // 初始每个学生至少1份
            Arrays.fill(candiesClockwise, 1);
            int current = (start + 1) % n; // 从起点下一个位置开始
            while (current != start) {
                int prev = (current - 1 + n) % n; // 左侧相邻位置（避免负数）
                if (scores[current] > scores[prev]) {
                    candiesClockwise[current] = candiesClockwise[prev] + 1;
                } else if (scores[current] == scores[prev]) {
                    candiesClockwise[current] = candiesClockwise[prev];
                }
                current = (current + 1) % n;
            }

            // 2.2 逆时针遍历（从起点向左）：确保当前学生 >= 右侧学生（按规则）
            int[] candiesCounterClockwise = new int[n];
            // 初始每个学生至少1份
            Arrays.fill(candiesCounterClockwise, 1);
            current = (start - 1 + n) % n; // 从起点前一个位置开始（避免负数）
            while (current != start) {
                int next = (current + 1) % n; // 右侧相邻位置
                if (scores[current] > scores[next]) {
                    candiesCounterClockwise[current] = candiesCounterClockwise[next] + 1;
                } else if (scores[current] == scores[next]) {
                    candiesCounterClockwise[current] = candiesCounterClockwise[next];
                }
                current = (current - 1 + n) % n;
            }

            // 2.3 取两个方向的最大值（同时满足左右两侧约束），计算总零食数
            int total = 0;
            for (int i = 0; i < n; i++) {
                total += Math.max(candiesClockwise[i], candiesCounterClockwise[i]);
            }

            // 2.4 更新最少总零食数
            if (total < minTotal) {
                minTotal = total;
            }
        }

        return minTotal;
    }

    // 测试样例
    public static void main(String[] args) {
        // 题目中的7组测试用例
        int[][] testCases = {
                {1, 2, 3},
                {2, 2, 3},
                {5, 5, 5, 5},
                {4, 3, 2, 1},
                {3, 1, 2, 2, 4},
                {2, 1, 3, 3},
                {1, 3, 2, 4}
        };

        // 执行测试并输出结果
        for (int i = 0; i < testCases.length; i++) {
            int[] scores = testCases[i];
            System.out.print("输入：scores = [");
            for (int j = 0; j < scores.length; j++) {
                System.out.print(scores[j]);
                if (j != scores.length - 1) {
                    System.out.print(", ");
                }
            }
            System.out.printf("]\n答案：%d\n\n", minCandies(scores));
        }
    }
}