P2655. 回转寿司

解题思路

本题是在环型数组中计算每一个元素右侧的下一个更小元素，显然应该使用单调栈来完成。本题和 经典题型. 下一个更大元素 II 以及 【单调栈】2025A-阿里巴巴找黄金宝箱(4) 的方法非常类似。

环型数组处理技巧

处理环型数组，一个常见的技巧是将数组 nums 进行拼接，然后对拼接后的数组进行单调栈操作，找到每一个元素右边的第一个更小元素即可。

对于范围落在 [0, 2*n-1] 的索引 i，为了得到在原数组中的索引 idx，我们可以对 i 进行求余操作来获得。

即 idx = i % n 就可以得到对应原数组中的索引。

答案计算方式

注意到一个问题，本题所需要计算的内容是每一个元素加上右边第一个更小元素的结果。可以有两种处理方式：

1. 初始化答案数组为原数组的一个拷贝（这样就可以避免最小值的额外更新），每次更新答案将 ans[idx] 更新为 nums[idx] 加上右边第一个更小元素。 2. 初始化一个新的长度为 n 的数组 help 仅用于储存每一个元素右边第一个更小元素，每次更新答案都仅更新 help 数组。最终遍历结束后将 help 中的每一个元素和 nums 中对应元素进行相加，即为答案数组。

后续写法采用是第一种处理方式，但或许第二种处理方式更加简单易懂，感兴趣的同学可以试一试。

暴力解法说明

PS：由于数据范围最多只有 500，所以 O(n²) 的暴力解是可以接受的。不熟悉单调栈的同学在考试遇到可以尝试使用暴力解。

代码

解法一：正序遍历写法